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 .
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
There are, in fact, two non-isomorphic graphs with these degree sequences.
(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:
which can be achieved by the following two non-isomorphic graph:
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.