Acyclic graph must have a leaf

Question

It is a theorem that every acyclic graph must have a leaf, ie. A vertex with degree 1 at most.

Intuitively, it makes sense as any vertex with more degree would be connected to at least 2 vertices and thus there wold be no way to break a cycle.

But how would this be proved?

Answer 1

Suppose there exists a acyclic graph with no leaf. Consider the longest path in this graph where no vertex is visited more than once. Let the end-vertices be x and y.

x and y must not be adjacent, nor can they be adjacent to more than one of the vertices in the path (otherwise a cycle will be formed). However, x and y are not leafs (leaves?) so they have to be adjacent to another vertex each which is not in the longest path in the graph. Hence, the path can be lengthened, and a contradiction is found.

Answer 2

Assume $G$ is a (finite) acyclic graph which doesn't have any leaves. Then every vertex is connected to at least two other vertices. Since $G$ is finite, there will have to form (possibly multiple) cycles, which is in contradiction to our assumption ''$G$ is acyclic''

The whole argument of course won't work if $G$ is infinite, then just imagine a 'straight line' of vertices, which is certainly acyclic and doesn't have any leaves.

EDIT: Let $V=\{v_1,\ldots,v_n\}$ be the set of vertices of $G$. Assume for this case $\deg(v_i)=2$ for all $i$, the argument will be the same for larger degrees for some vertices. Now start at a vertex, say $v_{i_1}$. Now 'walk' over one of the edges connected to $v_{i_1}$ to a vertex $v_{i_2}$. Since the degree of $v_{i_2}$ is $2$, you can walk to the vertex $v_{i_3}\neq v_{i_1}$, and continue this process. Now we use the fact that $G$ is finite. Because at a given point, say $N$, we will have to connect $v_{i_N}$ to $v_{i_1}$, since, if we would not find such an $N$, we are going on infinitely long, contradicting the fact that $G$ is finite. So $G$ contains a cycle $(v_{i_1},\ldots,v_{i_N})$, which contradicts the assumption

Answer 3

Note that a leaf is usually defined as a vertex of degree exactly $1$ (which is the definition I'll use).

If $G$ is a connected, finite, acyclic graph (i.e., a tree) with $n>1$ vertices and $m=n-1$ edges, then $G$ has at least $2$ leaves.

This is easily seen using the handshaking lemma: $$\sum_{v\in V(G)}\deg(v)=2m=2n-2.$$ If $\deg(v)\geq 2$ for all vertices, then we get $$2n\leq\sum_{v\in V(G)}\deg(v)= 2n-2,$$ which is absurd. So $G$ has at least one leaf. But if $G$ had exactly one leaf, then a similar argument implies $2(n-1)+1=2n-1\leq 2n-2$, again an impossibility. Thus $G$ has at least two leaves.