Introduction to graph theory/Proof of Theorem 2

From Wikiversity

< School:Mathematics/Undergraduate/Pure Mathematics < School of Mathematics:Introduction to Graph Theory

[edit] Statement

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.

[edit] Proof

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 1 v 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.

[edit] Comments

Introduction to graph theory/Proof of Theorem 2

From Wikiversity

[edit] Statement

[edit] Proof

[edit] Comments

Views

Personal tools

Search

Navigation

Community

Toolbox