For k ≥ 2, prove that a graph with at least k+1 vertices is k-connected if and only if for every T is a subset of S is a subset of V(G) with |S|=k and |T|=2, there is a cycle in G that contains T and avoids S-T.

Printable View

- October 27th 2008, 01:33 PMmndi1105Graph Theory [Lick 1973]
For k ≥ 2, prove that a graph with at least k+1 vertices is k-connected if and only if for every T is a subset of S is a subset of V(G) with |S|=k and |T|=2, there is a cycle in G that contains T and avoids S-T.