126 CHAPTER 2 Discrete Mathematics
be a path fromv tov′, where each
{vi− 1 ,vi} is an edge inG. Assume
thatv′is adjacent to another vertex
v′′. If a minimal length path from
vtov′′must travel throughv′, then
v′′must be of greater distance from
vthan isv′. This can’t happen and
so there must be a path fromvtov′′
which doesn’t pass throughv′. But
with{v′,v′′}being an edge, then we
see that it is possible to construct a
cycle throughv′, which is a contra-
diction.
We now may remove the vertexv′and the unique edgeeonvfrom
the graphG; what results is clearly a tree withn−1 vertices. Using
induction, we may conclude that this tree must haven− 1 −1 =n− 2
edges. If we replace the removed vertex and edge, we arrive at the
conclusion thatGitself must haven−1 edges.
Conversely, assume thatGis a connected graph withnvertices and
n−1 edges.
Claim: The graphGmust contain an end vertexv. If not then each
vertex ofGmust sit on at least two edges, and so
# edges inG =^12∑
verticesv
inG(# edges onv) ≥n,which is a contradiction. Therefore,Gmust contain an end vertexv.
We now remove the end vertex v and the single edge containing v
from the graphG. This results in a connected graphG′consisting of
n−1 vertices andn−2 edges. Again using mathematical induction we
conclude thatG′ must, in fact, be a tree. But then addingvand the
single edge toGwill certainly produce a tree, and we’re done.