- Sea T un bosque de orden
$n$ , tamaño$m$ y$k$ componentes. Pruebe que$m = n − k$ . - Sea
$T$ un árbol de orden$n$ que solo contiene vértices de degree 1 o 3. Pruebe que$T$ contiene$(n − 2)/2$ vértices de degree 3. - Pruebe que si una arista es insertada entre 2 vértices no adyacentes de un árbol, el grafo resultante contiene exactamente un ciclo.
- Pruebe que todo árbol en un grafo bipartito.
- Sea
$G$ bipartito y regular de grado$k$ , entonces existen$k$ emparejamientos perfectos disjuntos. - Sea
$G$ de orden$n$ (par), tal que para todos$v,w$ no adyacentes$d(v)+d(w)\geq n-1$ . Pruebe que existe un emparejamiento perfecto en$G$ . - Pruebe que un árbol tiene a lo sumo un emparejamiento perfecto.
-
$G$ tiene una cadena de Euler si y solo si exactamente 2 nodos son de degree impar. - La longana más larga posible en el dominó es de 51 fichas
- Sea
$G$ conexo tal que toda arista está contenida en un número impar de ciclos. Pruebe que$G$ es euleriano. - Si
$G_1$ y$G_2$ son grafos obtenidos de$G$ con$n \geq 3$ agregando iterativamente pares de vértices no adyacentes tales que sus degrees sumen al menos n, entonces G1 = G2. - Si
$G$ orden 3 o mayor. Pruebe que$G$ es hamiltoniano si solo si$cl(G)$ también lo es. - Si
$G$ es conexo, bipartito y regular de grado$k$ entonces es 2-conexo. - Pruebe que
$K_{n,n+1}$ es no hamiltoniano para todo$n\geq 1$ . - Sea
$G$ un subgrafo abarcador de$K_{n,n}(n\geq 2)$ cuyas particiones son$V_1$ y$V_2$ . Sean$u\in V_1$ y$v\in V_2$ tales que$d(u)+d(u)\gt n$ . Pruebe que$G$ es hamiltoniano si solo si$G+uv$ también lo es. - Pruebe que el grafo de Petersen es no hamiltoniano.
