Introduction to graph theory/Proof of Theorem 2

Statement

edit

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

Proof

edit

Suppose you have a graph   which is not a forest. Since a forest is defined to be a graph containing no cycles, it is clear that   must have a cycle  . All cycles have at least three vertices. Let   (with  ) be the vertices on   in order. Then there are two distinct  -paths, namely   and  .

Now suppose that   is a forest, but has two distinct  -paths, namely   and  . We would like to say that these create a cycle  . However, a cycle can only include each vertex once, and it is possible that one of the   is equal to one of the  . To that end, write   and  . Let   be the largest value of   such that   for some  . Then we find a cycle, namely  . By our choice of  , clearly no vertex appears more than once.

Comments

edit