11.11. Forests & Trees 353
(b)Verify that for any two verticesx¤yofH 3 , there are 3 paths fromxtoyin
H 3 , such that, besidesxandy, no two of those paths have a vertex in common.
(c)Conclude that the connectivity ofH 3 is 3.(d)Try extending your reasoning toH 4. (In fact, the connectivity ofHnisnfor
alln 1. A proof appears in the problem solution.)
Problem 11.26.
A set,M, of vertices of a graph is amaximal connectedset if every pair of vertices
in the set are connected, and any set of vertices properly containingMwill contain
two vertices that are not connected.
(a)What are the maximal connected subsets of the following (unconnected) graph?(b)Explain the connection between maximal connected sets and connected com-
ponents. Prove it.
Problem 11.27. (a)Prove thatKnis.n 1/-edge connected forn > 1.
LetMnbe a graph defined as follows: begin by takingngraphs with non-
overlapping sets of vertices, where each of thengraphs is.n 1/-edge connected
(they could be disjoint copies ofKn, for example). These will be subgraphs ofMn.
Then picknvertices, one from each subgraph, and add enough edges between pairs
of picked vertices that the subgraph of thenpicked vertices is also.n 1/-edge
connected.
(b)Draw a picture ofM 4.