Introduction to graph theory/Proof of Theorem 2

From Wikiversity
Jump to navigation Jump to search

Statement[edit | edit source]

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

Proof[edit | edit source]

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 | edit source]