Introduction to graph theory/Proof of Theorem 5

From Wikiversity
Jump to navigation Jump to search

Statement[edit | edit source]

A tree of order has edges.

Corollary of[edit | edit source]

Theorem 4:For a graph , the following are equivalent:

  • is a tree
  • is a minimal connected graph, in the sense that the removal of any edge will leave a disconnected graph.
  • is a maximal acyclic graph, in the sense that the addition of any missing edge will create a cycle.

Proof[edit | edit source]

For , all graphs have edges. For , there are two graphs, one with an edge and one without. The graph without an edge is disconnected, and therefore is not a tree, whereas the one with an edge is connected and has no cycles and therefore is a tree.

For , there are 4 graphs, one each with 0, 1, 2 or 3 edges. The graphs with 0 and 1 edges are disconnected, while the graph with 3 edges has a cycle. The graph with 2 edges is connected and has no cycle, so the theorem is proved for .

Now suppose we have proved this theorem for all , and let be a tree of order . Remove an edge from to form a new graph . By Theorem 4, is a minimal connected graph, and hence is disconnected. Any connected component of (by the connectedness of ) must have one of the vertices of in it, and hence has exactly two components.

The two components are connected, and have no cycles, and are therefore trees. Let there be vertices in the two components of . Then . Further, there are edges in the components, so has edges in total. Therefore, putting edge back into the graph, has edges.

Comments[edit | edit source]