SECTION 2.2 Elementary Graph Theory 125
spanning treeof the graph.^33 The second says that we are looking
for aminimal-weight spanning tree.
Before continuing with the above example, a few comments are in
order. First of all, a given graph is called atreeif it is connected, has
no multiple edges, and contains no cycles. Therefore, in particular, a
tree is a simple graph. We shall prove a couple of results about trees.
Lemma.LetGbe a tree, and letE be an edge inG. Then the removal
ofEresults in a disconnected graph.
Proof. LetEbe on the verticesvandw. If the removal ofEdoesn’t
disconnectGthen there is a path fromv towwithout using the edge
E. Since we can get fromvto wviaE, we clearly have a cycle in the
graphG. Therefore, the removal of Emust result in disconnectingG.
Theorem. Let G be a finite simple connected graph containing n
vertices. ThenGis a tree if and only ifGhasn− 1 edges.
Proof. Assume thatG is a finite tree and fix a vertexv inG. For
any vertexw inGdenote byd(v,w) (thedistance from v to w) the
length of the shortest path fromvtow. SinceGonly has finitely many
vertices, there must exist a vertexv′ofmaximaldistance fromv.
Claim: v′ has only one edge on it, i.e., v′ is an end in the tree G.
Assume thatd(v,v′) =dand let
v=v 0 , v 1 , v 2 , ..., vd=v′(^33) It is easy to see that any connected finite graph contains a spanning tree. Indeed, suppose that
the treeTis a subgroup of the connected graphGhaving a maximal number of vertices. If these
aren’t all of the vertices ofG, then by the connectivity ofGone of the vertices of the tree must be
adjacent to a new vertex inG. Adding this vertex (and the corresponding edge) creates a larger
tree insideG, a contradiction. (Even if the graph has an infinite number of vertices, there still must
exist a spanning tree. The proof, however, uses what’s calledZorn’s Lemmaand is outside the
scope of these notes.)