1
$\begingroup$

Draw simple graphs whose vertices have the following degrees, or explain why no such graph exists. There may be more than one way to draw each of these. (a) 2, 2, 4, 4, 4, 4, 6 .

$\endgroup$
4
$\begingroup$

So as to let you have some of the fun, here is a hint. Can you make a graph with six vertices, whose degrees are $1,1,3,3,3,3$ and then use a seventh vertex with an edge to each vertex of the graph you have just drawn? Your first graph need not be connected.

$\endgroup$
2
$\begingroup$

There are, in fact, two non-isomorphic graphs with these degree sequences.

Two non-isomorphic graphs with the desired degree sequence

(The rightmost one reminds me of the millenium falcon.)

The simplifying observation here is that the vertex of degree $6$ must be adjacent to every other vertex. Thus, we can generate the graphs without this vertex, and add it in later.

Without the vertex of degree $6$, we have the degrees depicted below:

Degrees without the degree $6$ vertex

which can be achieved by the following two non-isomorphic graph:

Two non-isomorphic graphs with the simplified degree sequence

If the two vertices of degree $1$ are adjacent, then the rest of the graph must be a $K_4$. If the two vertices of degree $1$ are not adjacent, then the rest of the graph must be $K_4-ij$ for some edge $ij$ and the vertices $i$ and $j$ are adjacent to the vertices of degree $1$. (Note: It is not possible for the two vertices of degree $1$ to be adjacent to the same vertex.)

Then we add the vertex of degree $6$ back in, to obtain the desired result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.