How many graphs with 12 edges over the vertices $\{1,2,...,12\}$ have two vertices with a degree of 5?

The two vertices aren't neighbours: $\binom {10} 2 \binom 85 ^2 \binom {\binom 82} 2$. Explanation: choosing the two, then neighbours for each, then a place for the two edges that's left.

The two vertices are neighbours: $\binom {10} 2 \binom 8 4 ^2 \binom {\binom 82} 3$

In both cases there could be a third vertex with a degree 5 so we need to uncount it: $\binom {10} 3 \binom 7 3 ^3$, choosing the 3 and then since they're all neighbours to each other, choose another 3 neighbors for each, which is exactly 12 edges.

The total is: $\binom {10} 2 \binom 85 ^2 \binom {\binom 82} 2 + \binom {10} 2 \binom 85 ^2 \binom {\binom 82} 2 - \binom {10} 3 \binom 7 3 ^3$

Does this cover all the overcounting? Is there a way to know for sure?

  • $\begingroup$ First of all, are you counting up to isomorphism of graphs or are the graphs labelled? $\endgroup$ – Jernej Jun 19 '15 at 9:54
  • $\begingroup$ You have 12 vertices, not 10, so where are you getting all those ${10\choose2}$? $\endgroup$ – Gerry Myerson Jun 19 '15 at 10:31
  • $\begingroup$ Yeah there's a minus 2 to everything by mistake. @GerryMyerson $\endgroup$ – shinzou Jun 19 '15 at 16:30

I don't really get why you subtracted 2each times. For example when you count the number of graph with 3 vertices of degree 5 what I get is: $${12\choose 3}{9\choose 3}^3$$ Choose the three vertices that have degree 5. You know that they are neighbour hence there is 3 edges left to choose among the 9 vertices left and this 3 times (once for each vertex).

In the same way for the number of graph with 2 vertices with degree 5 I get:

First case the two vertex are neighbour: $${12\choose 1}{11 \choose 5}{5\choose 1}{10\choose 4}{E(10)\choose 3}$$ Choose the first vertex, then it's five neighbour, choose the second vertex among the neighbour, choose the 4 neighbour left for the second vertex. Last choose the 3 reaming edges among the other vertices. Here $E(10)=(9*10)/2$, is the number of edges in the complete graph with $10$ vertices.

Second two vertex are not neighbour: $${12\choose 1}{11 \choose 5}{6\choose 1}{10\choose 5}{E(10)\choose 2}$$ Choose the first vertex, then it's five neighbour, choose the second vertex among the 6 vertices that are not the first vertex nor one of its neighbour, then choose the 5 neighbour for the second vertex. Last choose the 2 reaming edges among the other vertices. Again $E(10)=(9*10)/2$, is the number of edges in the complete graph with $10$ vertices.

So I get:

$$ {12\choose 1}{11 \choose 5}{5\choose 1}{10\choose 4}{E(10)\choose 3}+{12\choose 1}{11 \choose 5}{6\choose 1}{10\choose 5}{E(10)\choose 2} $$ Which is equal to 90 billion and something (see here).

May be your solution was correct, but what I'm sure of it is that your explanation didn't convince me at all. As I said: Why ${10 \choose 2}$ and not ${12 \choose 2}$? Why ${{8\choose 2} \choose 2}$ correspond to "the place for the two edges that's left"?

  • $\begingroup$ Since there are 165,091,172,592 unlabelled graphs on 12 vertices (oeis.org/A000088) it seems unlikely that roughly half of these have two vertices of degree 5 and exactly 12 edges. Unless you are counting labelled graphs? $\endgroup$ – gilleain Jun 19 '15 at 10:12
  • $\begingroup$ @gilleain Yes it count labelled graphs. Sorry. It is actually quite tricky to get the result for unlabelled graphs since you have to count the number of non equivalent graphs ... $\endgroup$ – wece Jun 19 '15 at 13:40
  • $\begingroup$ @gilleain Actually for unlabelled graphs I don't see a better way than count all the possible cases. There are not so many. I would say around 50. $\endgroup$ – wece Jun 19 '15 at 14:28
  • $\begingroup$ Sounds about right. I've made a diagram of a simple approach to listing the cases by extending from the graphs with 10 edges and degree sequence [5,5,1,1,1,1,1,1,1,1,1,1,1] (there are 5). However, I then realised the need to extend the 9-edge disconnected graph, which is a bit more fiddly. Will post as an answer in a few hours. $\endgroup$ – gilleain Jun 19 '15 at 14:37
  • $\begingroup$ I have a minus 2 error that carried over everywhere. So it's enough to subtract the case of 3 vertices with a degree 5? $\endgroup$ – shinzou Jun 19 '15 at 16:36

Sorry to give a partial answer, but here is how I would find the cases for a subset of the (unlabelled) graphs.

Starting from the two situations you mention : the degree-5 vertices disconnected and connected to each other. In both cases, we can assume a degree sequence of [5, 5, 1, ... 1] with 10 1's. This might be clearer from a diagram:extending 10-edge cases

The key should explain, but these are the 5 cases from graphs with 10 edges. Unfortunately, we also have to consider extension of the one with 9 edges where the C subgraph is disconnected.


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.