12 Teoremas

Teorema (Euler):

$\sum_v d(v)=2m$

Teorema:

cada grafo tiene un número par de vértices con grado impar

Teorema:

cada grafo $G$ contiene un camino $P$ con $\Vert P\Vert\geq \delta(G)$, y cada grafo $G$ con $\delta(G)\geq 2$ contiene un ciclo $C$ con $\vert C\vert> \delta(G)$

Teorema:

si $G$ no trivial: $\kappa(G)\leq\lambda(G)\leq\delta(G)$

Teorema:

cada grafo $G$ con $\vert E\vert>1$ contiene un subgrafo $H$ con $\delta(H)>\epsilon(H)\geq\epsilon(G)$

Teorema:

$G$ es bipartido con $\vert V_0\vert\neq \vert V_1\vert$ $\qquad\Longrightarrow\qquad$ $G$ no es hamiltoniano

Teorema:

$\forall v,w\in V, vw\notin E: d(v)+d(w)\geq n$ $\qquad\Longrightarrow\qquad$ $G$ es hamiltoniano

Teorema:

$G$ es hamiltoniano $\qquad\Longrightarrow\qquad$ $\forall S\subset V : c(G\setminus S)\leq\vert S\vert$

Teorema:

decidir si un grafo $G$ es hamiltoniano es $NP$-completo

Teorema:

$G$ es bipartido $\qquad\Longleftrightarrow\qquad$ $G$ no contiene ciclos impares

¿Algoritmo que decide que $G$ es bipartido?

Teorema:

$G$ es euleriano $\qquad\Longleftrightarrow\qquad$ $G$ es conexo y $\forall v\in V: d(v) \;\;\mbox{es par}$

¿Algoritmo que calcule un recorrido euleriano?

Teorema:

$G$ $k$-conexo $\qquad\Longrightarrow\qquad$ $\vert E\vert\geq \lceil kn/2 \rceil$

Teorema (Whitney):

$G$ es 2-conexo ($\vert G\vert>2$) $\qquad\Longrightarrow\qquad$ $\forall v,w\in V \exists vPw,vQw: P\cap Q=\emptyset$

Es decir, existen dos caminos que no se intersecan entre todas las posibles parejas de vértices en $G$.

Teorema (Mader):

cada grafo $G$ con $\epsilon(G)\geq 4k$ contiene un grafo $k$-conexo como grafo parcial