Question

Let G be a graph with n vertices and n edges.

(a) Show that G has a cycle.

(b) Use part (a) to prove that if G has n vertices, k components, and n − k + 1 edges, then G has a cycle.

Answer 1

a) Let G be a graph with n vertices. If G is connected graph then as we know that a graph with n vertices and ( n-1) edges is tree , and If G is not connected, one of its connected components has at least as many edges as vertices so this component is not a tree and must contain a cycle, hence G contains a cycle

for example : graph has 4 vertices and 3 edges

then it does not contain any cycle in it .

now, in above graph if we add any edge in it , then number of edges becomes equal to number of vertices and must contain the cycle.

b) we have n vetices , k components and ( n - k + 1 ) edges.

let us take an example to prove this

in above example , we have k components and n verties .

and the edges is n - 1 - ( k - 1) = n - 1 - k + 1

= n - k edges

and now in above problem we have ( n - k + 1) edges with k components.

so if we add one edge and maintain the k components with n vertices then it will definitely contain cycle. { and above example have graph is star graph }