7.2 Paths, Cycles, and Connectivity 133aa
b b
c c
FIGURE 7.7. Selecting a path fromatoc, given a path fromatoband a path
frombtoc.
Is there a difference between connecting two nodes by a walk and con-
necting them by a path? Not really: If two nodes can be connected by a
walk, then they can also be connected by a path. Sometimes it is more
convenient to use paths, sometimes, to use walks (see Exercise 7.2.6).
LetGbe a graph that is not necessarily connected.Gwill have connected
subgraphs; for example, the subgraph consisting of a single node (and no
edge) is connected. Aconnected componentHis a maximal subgraph that
is connected; in other words,His a connected component if it is connected
but every other subgraph ofGthat containsHis disconnected. It is clear
that every node ofGbelongs to some connected component. It follows by
Exercise 7.2.7 that different connected components ofGhave no node in
common (otherwise, their union would be a connected subgraph containing
both of them). In other words, every node ofGis contained in a unique
connected component.
7.2.4Is the proof as given above valid if (a) the nodealies on the pathQ; (b)
the pathsPandQhave no node in common exceptb?
7.2.5 (a) We delete an edgeefrom a connected graphG. Show by an example
that the remaining graph may not be connected.
(b) Prove that if we assume that the deleted edgeebelongs to a cycle that is
a subgraph ofG, then the remaining graph is connected.7.2.6LetGbe a graph and letuandvbe two nodes ofG.
(a) Prove that if there is a walk inGfromutov, thenGcontains a path
connectinguandv.
(b) Use part (a) to give another proof of the fact that ifGcontains a path
connectingaandb, and also a path connectingbandc, then it contains a
path connectingaandc.