3
$\begingroup$

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)$

2 Answers 2

9

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.

4

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.

  • 0
    Ok i conclude that there's only 22017-12-12