Ejemplo de árbol con

Question

En mi clase de combinatoria, está este teorema :

T es un árbol $ \iff $ T tiene una arista menos que el número de vértices y es acíclica.

Estoy confundido porque me parece que si hay al menos un ciclo en el grafo, el grafo debe tener el mismo número de aristas y vértices... ¿Qué opinas? ¿Tienes algún ejemplo?

Answer 1

Consideremos el gráfico de 4 vértices $a,b,c,d$ que consiste en un triángulo en los vértices $a,b,c$ es decir, las aristas son $ab,ac,bc$ . Contiene 4 vértices y 3 aristas, pero no es un árbol.

Answer 2

Sí, nunca lo había notado, pero como mencionaste la condición acíclica puede ser reemplazada por "conectada". Se puede demostrar fácilmente por inducción en $n$ . Definimos la hipótesis : $$ \mathcal{H}_n : \{ \forall \text{ connected graph $ G $ with } |E(G)|=n \text{ and } |V(G)|=n-1, \ G \text{ is a tree}\}$$

Caso base $n=1$ . $G$ es un vértice aislado, es decir, un Árbol

Inducción Supongamos que $ \mathcal{H}_{n}$ es verdadera, y dejemos que $G$ sea un grafo conexo en $n+1$ vértices y $n$ bordes.

Supongamos que no hay vértices de grado 1, es decir $\forall v\in V(G),\ d(v)\geq 2$ . Entonces, por el lema de la mano $$ 2m = \sum_{i=1}^{n+1}d(i)\geq 2(n+1)$$ en contradicción con nuestra hipótesis sobre el número de aristas.

Por lo tanto, $\exists \ u \in V(G)$ tal que $d(u)=1$ (recuerde que como $G$ está conectado no podemos tener $d(u)=0$ ). Entonces consideremos el gráfico $G'=G\backslash\{u\}$ . Es un gráfico sobre $n$ vértices, $n-1$ bordes (porque $u$ tenía grado 1), y sigue conectado. Por tanto, por hipótesis de inducción, es un Árbol. Añadiendo un vértice, conectado a un solo vértice existente en un árbol, no podemos formar un ciclo, y entonces construimos otro árbol. Por lo tanto $G$ también es un Árbol, y $\mathcal{H}_{n+1}$ es cierto.

Conclusión $ \mathcal{H}_{0}$ es verdadera y $ \mathcal{H}_{n}\Rightarrow \mathcal{H}_{n+1}$ Por lo tanto $\mathcal{H}_{n}$ para todos $n\in \mathbb{N}$

Supongo que a veces la condición acíclica es más fácil de comprobar que la conectividad.