Statement

edit

A tree of order   has   edges.

Corollary of

edit

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

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