Two graph theory questios regarding degree sequences and symmetric graphs

Question

1. Find all the simple graphs having degree sequence (1,2,2,3,3,3) up to isomorphism. I've tried conducting the Havel-Hakimi Theorem in reverse. I thought that it would be a proper way to find all those simple graphs. However, I was able to come up with only one graph.

   Am I correct? Or am i missing some graphs on the way? If so, can you recommend any other way?

2. Prove that all simple regular graphs having five or less vertices are symmetric. And find an example of an asymmetric simple regular graph on six vertices.

I know that symmetric graphs are regular. However, i couldn't figure out any start point for this one.

Answer 1

We can find all the graphs with this degree sequence in four steps:

1. There is only one graph (allowing parallel edges) with degree sequence $3,3$, shown in the first diagram above.
2. There is only one graph (allowing parallel edges) with degree sequence $3,3,2$, shown in the second diagram. To see this: if the degree-$2$ vertex is adjacent to both other vertices, suppressing it should produce the graph from step 1. If it's adjacent to the same vertex twice, deleting it leaves a graph with degree sequence $3,1$, which cannot exist without loops.
3. There is only one graph (allowing parallel edges) with degree sequence $3,3,3,1$, shown in the first diagram. To see this: if the vertex of degree $1$ is deleted, it leaves a graph with degree sequence $3,3,2$, which must be the graph from step 2.
4. There are four simple graphs with degree sequence $3,3,3,2,2,1$. All such graphs are obtained from the graph in step 3 by putting two degree-$2$ vertices in the middle of existing edges. One vertex (in blue) must subdivide one of the two existing parallel edges. The second vertex has four places to go (in red). There are two other cases, but they're symmetric to the ones shown (by reflecting vertically).

For completeness, here are the four graphs we get in this way:

Answer 2

1. I did not know how to do it systematically, but I managed to solve your problem by random ad hockery. (Of course this way is recommended only for very small graphs, like the one you have here.) Let me call the vertices of degree $3$ the "high degree" vertices and the others "low degree" vertices.

First, there are at most $5$ edges joining high degree vertices to low degree vertices, so there are at least $2$ edges joining high degree vertices to each other. That is, the graph induced by the degree $3$ vertices is either a path $P_3$ (case I) or a triangle $K_3$ (case II).

In case I, the $5$ remaining edges must all join high degree vertices to low degree vertices. So the degree $1$ vertex is either joined to the midpoint (case Ia) or an endpoint (case 2a) of the path formed by the degree $3$ vertices.

In case II, the degree $1$ vertex is either joined to one of the degree $3$ vertices (case IIa) or not (case IIb).

As luck would have it, each of the four cases described above could be realized in just one way, up to isomorphism.

2. I find it hard to believe that there is an asymmetric simple regular graph on $6$ vertices. Here are all the simple regular graphs on $6$ vertices that I can think of.

$0$-regular: The empty graph $\overline{K_6}$.

$1$-regular: $K_2+K_2+K_2$.

$2$-regular: $C_6$ or $C_3+C_3$.

$3$-regular: $\overline{C_6}$ and $\overline{C_3+C_3}=K_{3,3}$.

$4$-regular: $\overline{K_2+K_2+K_2}=K_{2,2,2}$.

$5$-regular: $K_6$.

They all look symmetric to me. $C_2+C_4$ is asymmetric and regular, but it's not simple. $C_3+C_4$ is an asymmetric simple regular graph on $7$ vertices.