2
$\begingroup$

First of all, the graphs considered are undirected & parallel edges and loops are allowed.

My attempt : By handshaking lemma, $$\text{Sum of degrees of all vertices} = 2 (\text{Number of edges})$$

Thus we get $\frac {2+2+2+2+2+2}{2}=\text{Number of edges}=6.$

Therefore we have to find all nonisomorphic graphs with six vertices and six edges.

Then I formed six cases based on number of cycles in such nonisomorphic graphs. Each case was then divided into subcases where we count graphs with number of loops and parallel edges in it.

enter image description here

My question is whether there exist other counting techniques in such scenario?

$\endgroup$

2 Answers 2

4
$\begingroup$

Each one of those isomorphism classes can be represented as an integer partition of 6, that is, a way of writing positive numbers which add up to 6, where the order doesn't matter. For example your 3(i), 3(ii) and 3(iii) correspond to $2 + 2 + 2, 4 + 1 + 1$ and $3 + 2 + 1$ respectively. There is a well-understood theory of integer partitions which would allow you to, for example, compute the number of partitions of some large integer $n$ without having to explicitly write them out, and therefore to compute the number of nonisomorphic graphs with $n$ vertices all having degree 2. (In the $n = 6$ case that theory is probably overkill.)

$\endgroup$
2
  • $\begingroup$ Great! Isn't it that the number of integer partitions we are making of 6 in a particular case (for example case-3 as you said) are actually number of connected components of the graph in that case? $\endgroup$
    – Error 404
    Oct 28, 2017 at 5:31
  • $\begingroup$ Here after the partition we can construct the unique one nonisomorphic graph because here $2$-regular implies all components are cyclic. This is shown in this QA. This quora link shows it can be generalized to component (The generalization may be trivial because the proof is similar which also seems to be referred to in Peter Taylor's answer). Then we only need to care about the partition. $\endgroup$
    – An5Drama
    Jan 12 at 3:34
3
$\begingroup$

An alternative approach is given by Riddell's formula, which transforms the generating function for the number of connected graphs of $n$ vertices with property $P$ into the generating function for the number of graphs of $n$ vertices whose connected components have property $P$.

Here you appear to be working with unlabelled graphs, so the number of connected graphs of $n$ vertices with the property that each vertex has degree $2$ is $1$ (for $n \ge 1$ given your convention on loops), and we work with ordinary generating functions. We have1 g.f. $A(x) = x + x^2 + x^3 + \ldots = \frac{x}{1-x}$ for connected graphs. Then we get g.f. for all graphs of $\exp\left(\sum_{k=1}^\infty \frac{A(x^k)}{k} \right) = \exp\left(\sum_{k=1}^\infty \frac{x^k}{k(1-x^k)} \right)$.

This is even more overkill as an approach than going directly to the partition function, although it winds up in the same place, as witness the mention of the above generating function in OEIS A000041.


1 I'm brushing under the carpet some technicalities around graphs with $0$ vertices.

$\endgroup$
4
  • $\begingroup$ Interesting! +1 $\endgroup$
    – Error 404
    Oct 28, 2017 at 5:33
  • $\begingroup$ This is the column k=2 in oeis.org/A167625 $\endgroup$ Feb 23, 2023 at 17:01
  • $\begingroup$ I have some questions. 1. why does $1$ omitted in $A(x)$ expansion? In your comments, you seems to say that you skip "0 vertices", but $1$ means for $A(x^i)$ that $i$ doesn't occur in the partition of $n$ which doesn't mean "0 vertices". 2. What does $\exp\left(\sum_{k=1}^\infty \frac{A(x^k)}{k} \right)$ mean? It seems to be related with the Exponential generating function, but EGF has no $\exp(\ldots)$. Could you answer my confusion? Thanks beforehand. $\endgroup$
    – An5Drama
    Jan 12 at 4:08
  • $\begingroup$ I verified in this doc my understanding of the generating function for the integer partition which I learned before. $\endgroup$
    – An5Drama
    Jan 12 at 4:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .