[Math] Counting the number of disconnected graphs

combinatoricsgraph theory

The task is to calculate the number of permutations of graph that are connected and do not have cyclic edges or multiple edges where repetition of isomorphic graph is not allowed.

Eg : for nodes = 3 and edges = 2 answer is 3 which is :

1-2-3
1-3-2
3-1-2

What I came up with :

  1. Given a graph with N nodes and K edges has $ n(n-1)/2 $ edges in maximum.
  2. Hence the number of graphs with K edges is ${ n(n-1)/2 \choose k}$
  3. But the problem is that it also contains certain disconnected graphs which needs to be subtracted.

In order to find those disconnected graphs I made the following observations

Let disGraphs(x) denote the number of graphs where exactly 'x' vertices are disconnected from the original graph.

Consider the case N = 4, K = 3

possibleAnswers = ${ n(n-1)/2 \choose k}$
= 20

requiredAnswer = possibleAnswers – disGraphs(1) 

This '1' cannot be reduced further since it is not possible to 
separate 2 or more vertices from 4 vertex graph with exactly 3 edges

And there are exactly 4 such graphs where 1 vertex is separated which can be represented by 

A  B    A  B    A--B    A--B
 / |    |\      | /       \|
D--C    D--C    D  C    D  C

requiredAnswer = 20 – 4 = 16
Which can be verified by Cayley's Formula

Now the same observation applied to N = 5, K = 4

possibleAnswers = ${ n(n-1)/2 \choose k}$
= 210

requiredAnswer = possibleAnswers – (disGraphs(1) + disGraphs(2))

  1. 1 vertex can be disconnected in ${5 \choose 1}$ ways = 5
  2. 2 vertex can be disconnected in ${5 \choose 2}$ ways = 10

requiredAnswer = 210 – 15 = 195

Which contradicts to the answer evaluated by using Cayley's Theorem which is 125.

I want to which graphs am I missing to consider, or is there something that I am missing out.

Best Answer

With regards to what you are missing in the case $N = 5$, $K = 4$, there are many graphs with one disconnected vertex. As you computed, there are $\binom{5}{1} = 5$ ways to select which vertex should be disconnected. However, you still have to choose which $4$ edges to take on the remaining $4$ vertices.

Note that any graph with $4$ edges on $4$ vertices must be connected, because the largest disconnected graph on $4$ vertices is a triangle with a disconnected vertex, which has $3$ edges. Hence from the $\binom{4}{2} = 6$ possible edges, we can choose any $4$, giving $\binom{6}{4} = 15$ ways to select the edges.

Thus, including the choice of the disconnected vertex, there are $5 \cdot 15 = 75$ graphs with one disconnected vertex. Hence the number of connected graphs with $5$ vertices and $4$ edges is $$210 - 75 - 10 = 125,$$ as given by Cayley's formula.

Note that in general if a graph on $n$ vertices is connected and has $n-1$ edges, it must be a tree, and thus by Cayley's formula there are $n^{n-2}$ such graphs.

Related Question