Show that a graph G V E is a tree if and ony if G is cyclel

Show that a graph G = (V, E) is a tree if and ony if G is cycleless and |E| = |V | 1.

Solution

We\'ll prove that a nonempty connected graph with |V|-1 edges is a tree by induction on |V|. The base case is |V| = 1 and |E| = 0; this single-vertex graph is easily seen to be acyclic. For larger |V|, from the Handshaking Lemma we have that d(v) = 2|E| = 2|V|-2. So from the Pigeonhole Principle there exists a vertex v with d(v) < 2. We can\'t have d(v) = 0, or G wouldn\'t be connected, so d(v) = 1. Now consider the graph G-v; it has |V|-1 vertices and |E|-1 = |V|-2 edges, and by the induction hypothesis, it\'s acyclic. Adding back v can\'t create any new cycles because any cycle that enters v has no edge to leave on. So G is also acyclic.

Now we need to show that if we have more than |V|-1 edges, some cycle exists. We\'ll do this by showing that an acyclic connected graph has at most |V|-1 edges, by induction on |V|. For |V| = 1 we have at most |V|-1 = 0 edges whether we are acyclic or not; this gives us the base case for free. Now consider an acyclic connected graph with |V| > 1 vertices. Choosing some vertex v₀ and construct a path v₁, v₂, ... by choosing at each step a node v_i+1 that is a neighbor of v_i and that is not already in the path. Eventually this process terminates (we only have |V| vertices to work with) with some vertex v_k. If v_k is adjacent to some vertex v_j already in the path, where jk-1, then we have a cycle v_j...v_k. If v_k has a neighbor that\'s not in the path, then we could have added it. So it follows that v_k is adjacent only to v_k-1 and has degree 1. Delete v_k to get G-v_k an acyclic graph with |V|-1 vertices and |E|-1 edges. From the induction hypothesis we have |E|-1=|V|-2 implying |E|=|V|-1 for G.