2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by "repetition of isomorphic graph is not allowed"? Your three graphs on three vertices with two edges are all isomorphic. $\endgroup$ – Shagnik Aug 30 '16 at 13:52
  • $\begingroup$ By that I mean 1-2-3 and 3-2-1 are same $\endgroup$ – Mayur Kulkarni Aug 30 '16 at 14:47
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, actually I was using the case k = n-1 in order to prove/disprove my hypothesis. Anyways, is there any way I could generalise it for every k >= n ? $\endgroup$ – Mayur Kulkarni Aug 30 '16 at 16:07
  • $\begingroup$ There won't be as "nice" an answer. Some very detailed answers to this question can be found here: math.stackexchange.com/q/689526 $\endgroup$ – Shagnik Aug 30 '16 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.