Let G be a connected graph with n vertices and at least n ed

Let G be a connected graph with n vertices and at least n edges. Let C be a
cycle of G. Prove that if T is a spanning tree of G, then T^c, the complement
of T , contains at least one edge of C.

Solution

Let G be a connected graph with n vertices and at least n edges. Let C be a cycle of G

Suppose that T is a spanning tree of G. Then T contains exactly (n-1) edges.

Let Tc be complement of T.

If possible suppose that Tc does not contain any edge of C.

Then all edges of C are also edges of T. That means the spanning tree T contains the cycle C which is a contradiction. Because a tree should not contain a cycle.

So our supposition is false. Hence Tc contains at least one edge of C.