[Math] Find the number of pairwise non-isomorphic $(n − 2)$-regular graphs with $n$ vertices

combinatoricsdiscrete mathematics

Find the number of pairwise non-isomorphic $(n − 2)$-regular graphs with $n$ vertices (i.e.
graphs in which all vertices have degree $n − 2$).

Best Answer

Look at the complement, the missing edges! You get a graph where every vertex has degree 1. Now it is easy.

Related Solutions

Graph Theory – Number of Non-Isomorphic Regular Graphs with Degree 4 and 7 Vertices

Let $G$ be a $4$-regular graph on $7$ vertices, and let $\overline{G}$ be the complement of $G$. $\overline{G}$ is regular; what is its degree (what you called order in your question)? What do you know about regular graphs of that degree? They’re very easy to count, and since $G_1$ is isomorphic to $G_2$ iff $\overline{G_1}$ is isomorphic to $\overline{G_2}$, counting the complements is as good as counting the graphs themselves.

(Note that the answer depends greatly on whether you’re counting labelled or unlabelled graphs. Also, I’m assuming that you’re looking only at simple graphs, i.e., without loops or multiple edges.)

Added:

To see that counting the complements is good enough, let $\mathscr{G}_n$ be the set of all simple graphs on $n$ vertices, and let $\varphi:\mathscr{G}_n\to\mathscr{G}_n:G\mapsto\overline{G}$ be the map that takes each graph in $\mathscr{G}_n$ to its complement. Then show that $\varphi$ is a bijection, and that $G\in\mathscr{G}_n$ is $k$-regular iff $\varphi(G)=\overline{G}$ is $(n-1-k)$-regular.

Number of non-isomorphic graphs

In the complement, each vertex has degree $2$, so we have one of

$C_8$
$C_5+C_3$
$C_4+C_4$

I.e., we are looking for the number of ways to write $8$ as sum of (unordered) summands $\ge3$.

Best Answer

Related Solutions

Graph Theory – Number of Non-Isomorphic Regular Graphs with Degree 4 and 7 Vertices

Number of non-isomorphic graphs

Related Question