Demos para el final

Question 1

G es bipartito <=> G no contiene ciclos de longitud impar

Answer 1

-> si hay un ciclo es de long par
<- definimos dos particiones que la distancia a un vertice en una sea par y en otra impar y mostramos biparticion

Question 2

G grafo o multigrafo no dirigido sin vertices aislados.

G euleriano <=> G es conexo y todos sus vertices tienen grado par

Answer 2

-> cada vez que paso por un v entro y salgo
<- induccion, hago un ciclo y lo saco entonces me queda un grafo que por hipotesis es eulerianovich, y concateno los caminos

Question 3

En un grafo conexo G , v es vértice de corte sí y sólo sí existen u y
w ∈ VG , u != v != w , tal que todo camino de u − w contiene a v .

Answer 3

-> si saco v se desconecta y basta tomar un v de cada componente
<- si todos los caminos pasan por v, sacando v no hay camino entre u y w, entonces es disconexo, v es de corte

Question 4

G conexo

e es arista de corte <=> e no pertenece a un ciclo en G

Answer 4

-> por contrarreciproco, los extremos de e estan en un ciclo, asi que sacando e siguen conectados
<- por contrarreciproco, si no es de corte hay dos caminos y si hay dos caminos los uno y tengo un ciclo

Question 5

G k-conexo con k >= 3 –>

G-e es (k-1)-conexo

Answer 5

damos un conjunto W de k-2 vertices de G-e y queremos mostrar que G-e-W es conexo
Caso 1: x,y extremos de e
hay camino x-z si saco a y, hay camino y-z si saco a x.
hay camino x-y sacando a e
Caso 2: al menos 1 no es extremo de e
u extremo de e, saco u es conexo, hay un camino

Question 6

G conexo ->
kv(G) <= ke(G) <= delta

Answer 6

si sacamos delta aristas, lo desconecto (kv <= delta)
si un grafo es k-conexo, sacando k-1 aristas no se desconecta, luego ke >= k, (kv <= ke)

Question 7

Teo de Whitney

Answer 7

demo en conexidad. Lo que dice el teorema es que:

G conexo con 3 o mas vertices, G es 2-conexo <=>
para todo par de vertices u, v hay por lo menos dos caminos internamente disjuntos que los unen.

Question 8

sea hk(n) la minima cantidad de aristas para un grafo k-conexo con n vertices. Entonces hk(n) >= ceil( kn/2 )

Answer 8

usando euler y la desigualdad del delta y kv, despejando e se llega a la formula

Question 9

Teorema de Euler (v- e + r = 2) en un grafo plano, conexo.

Answer 9

por induccion en la cantidad de aristas. hacemos un grafo con k+1 aristas (sabiendo que funciona para k) y le sacamos una arista

queda el caso conexo y el disconexo y mostramos que ambos funcionan

Question 10

Suma de grado de regiones = 2e

Answer 10

cada arista es frontera de dos regiones por lo que cada arista aporta en 2 a la suma total de grados de las regiones

Question 11

G plano, conexo, simple con al menos 3 aristas ->

e <= 3v - 6

Answer 11

la frontera de cada region tiene al menos 3 aristas
-> suma de regiones >= 3r -> 2e >= 3r y usando el de euler (v - e + r = 2) se llega a la expresion

Question 12

Sea G un grafo plano, conexo y bipartito ->

e <= 2v - 4

Answer 12

la frontera de cada region tiene al menos 4 aristas
-> suma de regiones >= 4r -> 2e >= 3r y usando el de euler (v - e + r = 2) se llega a la expresion

Question 13

Dos bloques diferentes de un grafo G deben tener a lo sumo un vertice en comun

Answer 13

supongamos dos bloques B1 y B2 tienen mas de un vertice en comun. mostramos que B1UB2 es conexo sin vertices de corte lo que contradice la maximalidad de B1 y B2

Question 14

X(G+H) = X(G) + X(H)

Answer 14

como todos los vertices de H son adyacentes a todos los vertices de G en G + H, no se puede usar ningun color de G en H ni ninguno de H en G.

Question 15

G grafo simple –> x(g) <= ∆(G ) + 1

∆(G ) = max{ g(vi ) }

Answer 15

pintando secuencialmente los vertices con un color no utilizado por un vecino ya pintado, obtenemos un coloreo valido con a lo sumo ∆(G ) + 1 de colores, luego la minima cantidad es eso o menos

Question 16

Si G es un grafo con k vértices mutuamente adyacentes ⇒ X (G ) ≥ k

Answer 16

usar menos de k colores resultaria en un par de vertices de los k mutuamente adyacentes pintados del mismo color ABS! (principio del palomar)

Question 17

Sea G k- crítico entonces g (vi ) ≥ k − 1 para todo vi ∈ V.

Answer 17

saco el vertice, pinto con k-1 colores, vuelvo a meter el vertice, hay

Question 18

X(G) >= ceil( #V / α(G) )

Answer 18

como cada color pinta a lo sumo α vertices,
#V <= X(G) * α
pasamos dividiendo, tomamos ceiling y somos nosotros

Question 19

Todo árbol con por lo menos una arista tiene por lo menos dos vértices de grado 1.

Answer 19

Tomamos en el arbol un camino simple maximal, los extremos son vertices de grado 1 ya que sino no seria maximal, ademas no tiene ciclos y el grafo es finito asi que se termina en algun momento y no vuelve al primer vertice.

Question 20

Todo arbol con n vertices tiene n-1 aristas

Answer 20

Como no tiene ciclos, el grafo es plano entonces vale que v-e+r = 2
y como r = 1, nos queda que e = v-1

Question 21

Sea T un grafo con n vértices (sin lazos). Entonces las siguientes
afirmaciones son equivalentes:
1 T es un árbol.
2 T no contiene ciclos y tiene n − 1 aristas.
3 T es conexo y tiene n − 1 aristas.
4 T es conexo y toda arista es una arista de corte.
5 Todo par de vértices de T están conectados por exactamente un
camino simple.
6 T no contiene ciclos y T + e tiene exactamente un ciclo.

Answer 21

1->2) con el teo de euler
2->3) T tiene k componentes, e = n-k -> k = 1, es conexo
3->4) si saco una arista tengo n-2 aristas osea 2 componentes
4->5) de no ser asi habria un ciclo, contradiciendo que toda e corta
5->6) la adicion de cualquier arista forma ciclo (concatenando el camino que ya existia con la arista)
6->1) mostramos que es conexo suponiendo que hay 2 componentes, si agregamos una arista entre las dos componentes esta no forma ciclo ABS!

Question 22

Sea T un árbol con n vértices y sea G un grafo simple tal que
δmin(G ) ≥ n − 1 entonces T es un subgrafo de G

Answer 22

Por induccion en la cantidad de vertices
en la induccion, sacando una hoja, T-v es subgrafo, y como los grados son suficientes hay otro vertice en G adyacente a v, por lo que T es subgrafo

Question 23

Un árbol binario completo de altura h tiene 2 ^(h+1) − 1 vértices.

Answer 23

Sale por induccion aplicando la hi al subarbol izquierdo y derecho

Question 24

Sea T un árbol que resulta de aplicar DFS a un grafo G conexo, entonces
la raíz r de T es un vértice de corte de G sii r tiene más de un hijo en T .

Answer 24

-> suponemos que r tiene un solo hijo u -> el subarbol con u de raiz es recubridor de G-v -> G-v es conexo
<-hay dos hijos y por como funciona dfs, no hay aristas entre ningun ancestro/descendiente de ellos por lo que todos los caminos pasan por la raiz.

Question 25

Sea T un árbol que resulta de aplicar DFS a un grafo G conexo, entonces
un vértice v de T que no es raíz es un vértice de corte de G sii v tiene un hijo w tal que ningún descendiente de w está unido a un ancestro propio de v por una arista en G − T

Answer 25

ni idea

Question 26

Sea f un flujo en una red N y sea ⟨Vf , Vs ⟩ un corte. Entonces
val(f ) = Sumatoria de los flujos de ⟨Vf , Vs ⟩ -
Sumatoria de los flujos de ⟨Vs , Vf ⟩

Answer 26

tirar unas magias con la sumatoria de la definicion de val(f)