272 16. Answers to Exercises
connected to all the others, in particular to the node with degree 0, which
is impossible.
7.2 Paths, Cycles, and Connectivity
7.2.1. There are 4 paths, 6 cycles, and 1 complete graph.
7.2.2. The edgeless graph onnnodes has 2nsubgraphs. The triangle has
18 subgraphs.
7.2.3.The path of length 3 and the cycle of length 5 are the only examples.
(The complement of a longer path or cycle has too many edges.)
7.2.4. Yes, the proof remains valid.
7.2.5. (a) Delete any edge from a path. (b) Consider two nodesuand
v. the original graph contains a path connecting them. If this does not go
throughe, then it remains a path aftereis deleted. If it goes throughe,
then lete=xy, and assume that the path reachesxfirst (when traversed
fromutov). Then aftereis deleted, there is a path in the remaining graph
fromutox, and also fromxtoy(the remainder of the cycle), so there is
one fromutoy. But there is also one fromytov, so there is also a path
fromutov.
7.2.6. (a) Consider a shortest walk fromutov; if this goes through any
nodes more than once, the part of it between two passes through this node
can be deleted, to make it shorter. (b) The two paths together form a walk
fromatoc.
7.2.7.Letwbe a common node ofH 1 andH 2. If you want a path between
nodesuandvinH, then you can take a path fromutow, followed by a
path fromwtov, to get a walk fromutow.
7.2.8. Both graphs are connected.
7.2.9. The union of this edge and one of these components would form a
connected graph that is strictly larger than the component, contradicting
the definition of a component.
7.2.10. Ifuandvare in the same connected component, then this com-
ponent, and henceGtoo, contains a path connecting them. Conversely, if
there is a pathP inGconnectinguandv, then this path is a connected
subgraph, and a maximal connected subgraph containingPis a connected
component containinguandv.
7.2.11. Assume that the graph is not connected and let a connected
componentHof it haveknodes. ThenHhas at most
(k
2)
edges. The restof the graph has at most
(n−k
2)
edges. Then the number of edges is at most
(
k
2)
+
(
n−k
2)
=
(
n− 1
2)
−(k−1)(n−k−1)≤(
n− 1
2