Graph Theory & Permutations

Question

Given 3 connected components with 2,2,3 vertices. In how many ways can we add two edges to connect the whole graph?

Also, if possible generalise the method for graph with k connected components each having ni vertices.

Ans=84

Answer 1

Answer for the 1st part 

Let us assume that the given 3 components are C₁,C₂,C₃ .

Now, we have to find in how many ways we can join two edges between the connected components such that the whole graph becomes connected.

This can be done in the 3 ways

CASE 1 :  We join an edge between C₁ and C₂ and again an edge between C₂ and C₃

Now, C₁ has 2 vertices and C₂ has 2 vertices 

So, joining an edge between C₁ and C₂ can be done in 2*2 = 4 ways

Again C₃ has 3 vertices so joining an edge can be done in 2*3 = 6 ways

So, joining an edge between C₁ and C₂ and then an edge between C₂ and C₃ can be done in (4*6)ways = 24 ways

CASE 2: We join an edge between C₁ and C₃ and again an edge between C₃ and C₂

Now, joining an edge between C₁ and C₃ can be done in (2 * 3) ways = 6 ways (in the similar way shown in Case 1)

an edge between C₃ and C₂ can be done in ( 3 * 2) ways = 6 ways

So, joining an edge between C₁ and C3 and then an edge between C3 and C2 can be done in ( 6 * 6 ) ways = 36 ways

CASE 3: We join an edge in between C₂ and C₁ and again an edge between C₁ and C₃

In the similar way as in case 1 and case 2 this can be done in (2 * 2) * (2 * 3) ways = 24 ways.

So, the total number of ways to add two edges such that the graph becomes connected is (24 + 36 + 24) ways = 84 ways (ANSWER)

Answer for the 2nd part (Generalization)

Suppose we k components C₁,C₂,C₃,........C_k and let each of the k components has v₁,v₂,...v_k vertices

Now, let v_a1,v_a2,v_a3,....v_an be any arbitrary permutation of the numbers v₁,v₂,...v_k and let T_k is required number of ways to form a connected graph.

Then T_k = v₁ * v₂  for k=2

and T_k = 1/2 * ∑ (v_a1 * v_a2² * v_a3² * v_a4² *.....*v_a(n-1)²* v_an ) for k>=3