91Ó°ÊÓ

Show that the block graph of any connected graph is a tree.

Let \(G\) be a 2-connected graph but not a triangle, and let \(e\) be an edge of \(G .\) Show that either \(G-e\) or \(G / e\) is again 2-connected. Deduce a constructive characterization of the 2-connected graphs analogous to Theorem 3.2.2.

Let \(G\) be a 3-connected graph, and let \(x y\) be an edge of \(G\). Show that \(G / x y\) is 3-connected if and only if \(G-\\{x, y\\}\) is 2-connected.

Let \(k \geqslant 2\). Show that every \(k\)-connected graph of order at least \(2 k\) contains a cycle of length at least \(2 k\).

Show that \(k\)-linked graphs are \((2 k-1)\)-connected. Are they even \(2 k\) connected?