Graph Theory: Trees, leaves and cycles

Question

So, a vertex is called a leaf if it connected to only one edge.

a) Show that a tree with at least one edge has at least 2 leaves. b) Assume that G = (V, E) is a graph, V ≠ Ø, where every vertex has at least 2 edges, Show that G has a cycle.

I don't really know for sure how to write the proofs for these two tasks, but here is what I have

a) So between two points u, v in the graph there is always exactly one path, and if G is a tree it is connected. For a Graph with e=1 edges you will have n=e+1 vertices. Is there any more to it than this? Do I have to include something else?

b) So G is a connected graph iff G=(V,E{e}) has a cycle that contain {e}. Now, every node has the degree 2, meaning they are connected to vertices. This also means that the end vertex is connected to 2 vertices. Very simplified I have written

u,v ∈ V V = {u(n),......u(n+1), v} Now, if G did not contain any cycles that would be it, but since v is connected by 2 vertices it means it is reachable by another vertex than u(n+1) right? having a problem showing this in a sensible way.

Thanks in advance.

Answer 1

a) Trees are minimally connected, meaning the deletion of any edge disconnects the graph (into two nontrivial trees unless your graph is very special). By strong induction, these two trees each have at least two leaves. What can you conclude about the original tree?

b) Since every vertex has degree at least two, you could consider a subgraph wherein every vertex has degree exactly two. Do you know a famous result about graphs whose vertices are all of even degree?

Answer 2

To prove (b) let $v_0$ be any vertex. Since $\deg v_0\ge 2$, there is a vertex $v_1$ such that $\{v_0,v_1\}$ is an edge of $G$. Similarly, there is a vertex $v_2$ different from both $v_0$ and $v_1$ such that $\{v_1,v_2\}$ is an edge of $G$. Keep going: given $v_{k-1}$ and $v_k$, there is a $v_{k+1}$ different from both $v_{k-1}$ and $v_k$ such that $\{v_k,v_{k+1}\}$ is an edge of $G$, and if possible we’ll choose $v_{k+1}$ to be different from $v_i$ for all $i\le k$. $V$ is finite, so eventually we’ll run out of unvisited vertices, and we’ll have to choose $v_{k+1}=v_\ell$ for some $\ell<k-1$. You know have a cycle: what is it?

You can prove (a) by induction on the number $n$ of vertices of the tree. First notice that (b) implies that every tree has at least one leaf; why? Now suppose that every tree with $n$ vertices has at least two leaves, and let $T$ be a tree with $n+1$ vertices. $T$ has a leaf $v$; let $T'=T-v$, the graph obtained from $T$ by removing $v$ and the one edge attached to it. Check that $T'$ is a tree and hence by the induction hypothesis has at least two leaves; then show that at least one of these leaves is also a leaf of $T$.

Answer 3

Here's an alternative to proving a). As you already mention, a tree on $n$ vertices has $n-1$ edges. If the local vertex degrees are $d_1,\dots,d_n$, then twice the number of edges is the sum of the vertex degrees. (This is true for any graph - every edge gets counted exactly twice in the sum of degrees, once for each vertex it is incident to.) So we have $$ 2n-2 = \sum_{j=1}^n d_j.$$

We can rewrite this as $$ \sum_{j=1}^n (2-d_j) = 2.$$

If the tree has more than one vertex, then (since the tree is connected), all vertex degrees must be at least 1. So the terms of the sum on the left are all integers $\leq 1$, and so at least two of these must be positive, meaning that $d_j=1$.

For (b), it depends on what you know. Here are a few direct ways:

• If you already know that a tree is precisely a connected graph that has no cycle, then this is immediate from the above, since your graph has no vertices of degree 1, so isn't a tree.
• If you know that every connected graph contains a spanning tree, just observe that the number of edges exceeds the number of edges in your spanning tree $T$, and so there must be some additional edge connecting two different vertices $v$ and $w$ in your spanning tree. Combining this edge with the unique simple path in $T$ connecting $v$ and $w$, you have found a cycle. Note that this proves the previous statement also: Any connected graph on $n$ vertices with at least $n$ edges contains a cycle.

In terms of a direct proof that doesn't use anything, Brian's is probably as good as it gets.