Introduction to graph theory/Proof of Theorem 2

From Wikiversity
Jump to: navigation, search


Statement[edit]

A graph is a forest if and only if for every pair of distinct vertices u,v, there is at most one u,v-path.

Proof[edit]

Suppose you have a graph G which is not a forest. Since a forest is defined to be a graph containing no cycles, it is clear that G must have a cycle C. All cycles have at least three vertices. Let v_1, v_2, \ldots, v_n (with n\ge 3) be the vertices on C in order. Then there are two distinct v_1,v_2-paths, namely v_1v_2 and v_1v_nv_{n-1}\ldots v_3v_2.

Now suppose that G is not a forest, but has two distinct u,v-paths, namely ua_1a_2\ldots a_nv and ub_1b_2\ldots b_mv. We would like to say that these create a cycle ua_1\ldots a_nvb_mb_{m-1}\ldots b_1u. However, a cycle can only include each vertex once, and it is possible that one of the b_i is equal to one of the a_j. To that end, write a_0=b_0=u and a_{n+1}=b_{m+1}=v. Let i be the largest value of i<=n such that a_i=b_j for some j. Then we find a cycle, namely a_ia_{i+1}\ldots a_nvb_mb_{m-1}\ldots b_j. By our choice of i, clearly no vertex appears more than once.

Comments[edit]