Sorry I'm new here, can someone please help me out with this question. I missed a couple of lectures and I don't even know where to start. I'm trying to find all the non-isomorphic graphs whose degree sequence is $(6,3,3,3,3,3,3)$
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Hint: Imagine a central vertex with degree 6 connected to the other six vertices (say, arranged on a circle). To get the vertices on the circle to have degree 3, each one must be connected to two others on the circle. If we label the vertices on the circle $v_1$ to $v_6$, then, without loss of generality, $v_1 \sim v_2$ and $v_2 \sim v_3$. After that, you have some freedom in adding edges.
Try it! See how many nonisomorphic ways you can find to fill in the missing edges.
I’m going to assume that you’re intended to consider only simple graphs, i.e., graphs with no loops and no multiple edges.
The key is the vertex of degree $6$: there are only six other vertices, so it must be connected to each of the others. That gives you a sort of asterisk, or six-pointed star:
Each of the other vertices needs two more edges, and clearly none of those edges can go to the central vertex: it’s done. Clearly you could connect the outer vertices in a ring to make a sort of six-spoked wheel; can you find any other way to give each a degree of $3$?
If you’re allowed loops or multiple edges, the problem becomes significantly more complicated.