Find all pairwise non-isomorphic graphs with the degree sequence (2,2,3,3,4,4)

Question

I'm not sure when I know if I've found them all. Is there a good way to check if they're non-isomorphic as well, or an easy way to approach a question like this in general?

Answer 1

It's like a proof by cases. Are the two vertices of degree $4$ adjacent? If not, each is adjacent to all the other vertices. That takes care of the degree-two vertices, so the degree-three vertices must be adjacent to each other. There is clearly only one isomorphism class in this case.

Now you have to assume that two degree-four vertices are adjacent. Try to divide all the possibilities into cases in some useful fashion. There are only $4$ edges left, and each of the degree-four vertices is adjacent to $3$ of them, so there are only a few possibilities.

1. Each degree-four vertex is adjacent to both the degree-two vertices and one of the degree-three vertices.

2. Each degree-four vertex is adjacent to both the degree-three vertices and one of the degree-two vertices.

3. One degree-four vertex is adjacent to both the degree-two vertices and the other is adjacent to both degree-three vertices.

Now you have to see what the implications of each of these possibilities is. Some may lead to more than one additional choice, and some may be impossible.

Answer 2

I am assuming you want simple graphs with no loops or multiple edges. For the two vertices of degree two you can remove the vertex and the two directly adjacent edges giving a reduced simple graph. This now leaves the reduced graph with four vertices. The two degree two vertices could have been adjacent or else not adjacent.

In the case they were adjacent, the reduced graph has two vertex degrees decremented and they must be the degree four vertices leaving the complete graph with each vertex of degree 3. The original graph is the complete graph with four vertices and one edge has a length three path added joining its two endpoints.

In the case they were not adjacent, thre are three subcases. In the first subcase, the two degree two vertices are adjacent to the same pair of vertices and these must be the degree four vertices. The reduced graph is the complete graph on four vertices with one edge removed. The original graph is the complete graph with four vertices and one edge is replaced with a pair of length two paths.

The second subcase is that the two degree two vertices are adjacent to three vertices and one of them is adjacent to both. This vertex in the reduced graph is of degree two. The original graph is the complete graph with four vertices and one of them has one of its edges replaced with a length two path and another of its edges will have a length two path added joining its two endpoints.

The third subcase is the the two degree two vertices are adjacent to two pairs of disjoint vertices. In this case there are two further subsubcases. In one subsubcase the two degree two vertices each are adjacent to a degree three and a degree four vertex. Here the original graph is built from a pair of vertices joined by an edge, the two new vertices are each joined to the original two, and pick a disjoint pair of new edges and adjoin a path of length two each one of them.

In the last subsubcase the original graph is the complete graph on four vertices with a vertex added to one edge and the unique disjoint edge of that has a path of length two adjoined to it.

In general, it will be a tricky process involving multiple cases and you have to be very careful to find all the different cases. In my first attempt, I only found one case. For an easier example, see my answer to MSE question 2569083. An alternative way is to consult a list of all graphs with a fixed number of vertices and select all those with a given degree sequence. Of course, this method requires having the list of graphs available, but this is possible for small number of vertices. Another answer shows how to do this for your graph.

Answer 3

We can use Nauty's geng and showg commands to generate non-isomorphic $6$-vertex $9$-edge graphs with degrees between 2 and 4.

./geng 6 9:9 -d2 -D4 | ./showg

This generates 11 graphs, and we can filter out the ones with an incorrect degree sequence.

Writing a script, this gives the following 5 graphs:

(The vertices are marked with their degrees.)

Answer 4

The complement of a graph with degree sequence $(4,4,3,3,2,2)$ is a graph with degree sequence $(3,3,2,2,1,1).$ Inasmuch as graphs are isomorphic if and only if their complements are isomorphic, the problem of finding the nonisomorphic graphs with degree sequence $(4,4,3,3,2,2)$ is equivalent to the problem of finding the nonisomorphic graphs with degree sequence $(3,3,2,2,1,1).$ I find it easier to consider the latter problem, because graphs with $6$ edges are easier for me to draw and visualize than graphs with $9$ edges.

Consider a graph with degree sequence $(3,3,2,2,1,1).$ There are seven cases:

I. The vertices of degree $1$ are adjacent to each other.

II. The vertices of degree $1$ are both adjacent to the same vertex of degree $2.$

III. The vertices of degree $1$ are both adjacent to the same vertex of degree $3.$

IV. The vertices of degree $1$ are adjacent to two different vertices, one of degree $2$ and the other of degree $3.$

V. The vertices of degree $1$ are adjacent to two different vertices, both of degree $2.$

VI. The vertices of degree $1$ are adjacent to two different vertices, both of degree $3,$ and the vertices of degree $3$ are adjacent to each other.

VII. The vertices of degree $1$ are adjacent to two different vertices, both of degree $3,$ and the vertices of degree $3$ are not adjacent to each other.

You can easily convince yourself that cases II and V are impossible, and each of the five remaining cases has a unique realization up to isomorphism.