Preface
I am currently preparing for applied mathematics and informatics olympiad qualifiers in my university, and while preparing I have stumbled upon the following task, which is quite hard for me to deal with.
The problem
How many strict undirected graphs with $8$ vertices each of degree $5$ are there (up to algebraic isomorphism)? Draw at least one of them, showing if it is planar or not.
My attempt
I was able to create exactly $3$ graphs of the above construction, knowing that any graph of such construction has $|E|=\frac{8\cdot 5}{2}=20$, and have shown that each of them has a subgraph homeomorphic to $K_{3,3}$ (so none of them are planar).
Below I have attached the image of these three graphs with red edges showing a $K_{3, 3}$-homeomorphic subgraph for each of the graphs. Yet, I cannot think of any other graphs, which would follow the problem's proposed structure. As it seems to me, each of these graphs have their edges starting from any vertex iteratively shifted from closest to farthest vertices (I do not really know how to describe it in better words). It also seems like each of the graphs has a Hamiltonian path.
The answer for the first part of the problem (number of such graphs possible) is $3$. It seems to comply with the fact that I cannot come up with any other graph constructions except the ones I have already created. Yet, I cannot devise any formal solution to prove that there are no more than $3$ such graphs. And so I wonder: is there any formal way to show this?
Any help will be appreciated, thank you in advance!
Best Answer
Using the idea proposed by @IvanNeretin, we can come up with a reinterpretation of the initial task.
Our original problem regarded finding the number of unique graphs, such that $G_i(V, E):~|V|=8,~\forall v \in V:~\deg(v)=5$.
Let us now recall that in the $K_8(V_K, E_K)$ graph $\forall v \in V_K:~\deg(v)=7$. Let us also note that every uniquely defined graph $G(V_G,E_N)$ of order $M$ with size $N$ has a corresponding unique complementary graph $G'(V_{G'}, E_S)$, in which two distinct vertices will be adjacent iff they are not adjacent in $G$. The number of edges in $G'$ is $S=|E_S|=|E_K \setminus E_N| = K - N$.
Now, from the definition of $G'$ it can be derived that $\forall v' \in V_{G'},~v \in V_G$, s.t. $v'\equiv v$: $\deg(v')=\max\deg(V_G) - \deg(v)$. Hence, now we can reformulate the original task in the following manner: "How many graphs $G'_i$ of order $8$ are there, such that degree of every vertex in it is $2$", since there is a unique complementary graph for every one of the original construction.
Now, let us note that since the reformulated task demands degree of every vertex of $G'_i$ being $2$, then every $G'_i$ consists of cycles. Cycles are much easier to deal with than graphs of order $8$ with every vertex of degree $5$. Let us also note that since the minimal cycle is $C_3$, there are exactly $3$ ways to compose $G'$ from cyclical subgraphs, such that their cumulative order is 8:
Now, recalling that each of the above graphs uniquely correspond to an own-complement of order $8$ which have degree of every vertex being $5$, we can conclude that since we have shown all possible ways to compose such graphs, the answer for the original problem is $3$.
Showing that none of the original graphs are planar can be done through highlighting respective $K_{3,3}$ or $K_5$ subgraphs in them.