10 Bosques y árboles

• si $G$ no tiene ciclos, $G$ es un bosque
• si $G$ es un bosque y conexo, $G$ es un árbol
• los componentes conexos de un bosque son árboles

Teorema:

las siguientes propiedades son equivalentes:

• $G$ es un árbol
• entre cada pareja de vértices existe un camino único
• cada arista es un puente
• $G$ es acíclico y $n=m-1$
• $G$ es conexo y $n=m-1$
• $G$ es acíclico y maximal en $\vert E\vert$
• $G$ es conexo y minimal en $\vert E\vert$

Vocabulario:

árbol con raíz	un árbol con un vértice marcado como raíz
árbol libre	un árbol sin marca en ningún vértice
árbol generador	$T$ es árbol generador de un grafo $G$,
	si $T\subseteq G$ y $V(T)=V(G)$

Teorema:

cada grafo $G$ contiene un bosque generador, y si $G$ es conexo, contiene un árbol generador (cuya raíz puede ser cualquier vértice)