11.11. Forests & Trees 357
graph,G, is connected. This completes the proof of the inductive case, and the
Claim follows by strong induction.
Problem 11.32.
LetGbe the graph formed fromC2n, the cycle of length2n, by connecting every
pair of vertices at maximum distance from each other inC2nby an edge inG.
(a)Given two vertices ofGfind their distance inG.(b)What is thediameterofG, that is, the largest distance between two vertices?(c)Prove that the graph is not 4-connected.(d)Prove that the graph is 3-connected.Problems for Section 11.11
Exam Problems
Problem 11.33.
Then-dimensional hypercube,Hn, is a simple graph whose vertices are the binary
strings of lengthn. Two vertices are adjacent if and only if they differ in exactly
one bit. Consider for exampleH 3 , shown in Figure 11.27. (Here, vertices 111 and
011 are adjacent because they differ only in the first bit, while vertices 101 and
011 are not adjacent because they differ in both the first and second bits.)
Explain why it is impossible to find two spanning trees ofH 3 that have no edges
in common.
Hint:Count vertices & edges.
Class Problems
Problem 11.34.
ProcedureMarkstarts with a connected, simple graph with all edges unmarked and
then marks some edges. At any point in the procedure a path that includes only
marked edges is called afully markedpath, and an edge that has no fully marked
path between its endpoints is calledeligible.
ProcedureMarksimply keeps marking eligible edges, and terminates when there
are none.
Prove thatMarkterminates, and that when it does, the set of marked edges forms
a spanning tree of the original graph.