Question

Show that if an undirected graph with n vertices has k connected components, then it has at least n - k edges.

Short answer

The undirected graph with n vertices has k connected components with least n - k edges.

Step-by-step solution

Two sub graph of main graph  

If there is no edge between two sub-graphs of a given graph, they are said to have linked components.

That is, no edge E ( u,v) exists in which u corresponds towards the set of vertices of the very first sub-graph plus v belongs to that same vertex set of the second sub-graph, or vice versa..

Step 2: Evidence via Induction

Proof for the Most Basic Case:

When k = 1, there is only one linked component in a network with n vertices. All of the vertices in the network are linked since there is only one connected component.

There are at least n - 1 edges in an undirected network with n linked vertices.

As a result, the number of edges in the graph is n - 1.

Since k=1, the value of n - k = n - 1 can be calculated.

As a result, the assertion is correct for k = 0.

Assumption

The assumption is,

Suppose that for n = v and k = c, the assertion is correct.

As a result, there are at least v - c edges in the undirected graph G with v vertices and linked components.

Demonstrate that the assertion is correct for n = v and k = c + 1.

The proof is,

• There are at least v - c edges in a graph G with vvertices and clinked components. (based on the assumption from Step 2)

• Split one of the linked components of the graph G into two to make a graph G1 with c + 1 connected components.

• Because there must be no edge between two linked components, one of the edges must be eliminated to make a new connected component.

• Inside the graphs G1, overall number of edges is at least v - c -1 or v - (c + 1) (Since the graph G had v - cedges).

• Inside the graph G1 , the number of linked elements has become equal to c + 1, and the number of edges is at least v- ( c+ 1 ).

Assuming n = vvertices as well as k = c + 1 linked elements, the following holds true.

As a result, it has been established.