Construct Pairs of Non Isomorphic Graphs

Question

I Have the following question :

Give three examples of simple, connected graphs, all with 8 vertices with degrees 2, 2, 2, 2, 3, 3, 4 and 4, no pairs of which are isomorphic

What is the best method to find such 3 graphs ? In general how can I proceed to find 2 or more non isomorphic Graphs that have the same numer of vertices with the same degree?

Thank you !

Answer 1

Hints: Each graph has two vertices of degree 4. Call them $a$ and $b$.

1. A graph where $a$ and $b$ share an edge cannot be isomorphic to a graph where $a$ and $b$ do not share an edge.

2. A graph where both of $a$ or $b$ share an edge with a vertex of order 3 is not isomorphic to a graph where only one does.

3. A graph where one of $a$ or $b$ is adjacent to all of the vertices of order 2 is not isomorphic to a graph where neither one is, or to a graph where both are.

4. Etc.

Answer 2

In general, you can define 0/1 variables $a_{ij}$ that say whether edge $(i,j)$ is in the graph, and code up the constraints on the degrees by saying that $\sum_j a_{ij} = deg(i)$ where $deg(i)$ is the degree of the $i$th vertex. This system of equations and inequalities gives you a polytope and the integer value points inside the polytope correspond to the graphs you can make that satisfy the vertex degree requirements. Then for each graph you can permute the vertices that have the same degree to get all isomorphic graphs, and the total number of equivalence classes you get is the total number of non-isomorphic graphs you can make. There is literature on listing integer points inside of polytopes if you're interested in this computational approach. However when you have many vertices that have the same degree, you'll get many isomorphic graphs so this approach is only viable when the number of vertices of each degree is relatively low (e.g. one vertex for most degrees) and/or the total number of vertices is not too large. But it should work for 8 vertices just fine.