# Drawing simple graphs using graph theory

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 .

-
Is it a homework? Then please put this tag, explain what have you tried and what are the problems. – Ilya Oct 28 '11 at 11:47
can a graph be drawn or not using the vertices? – susan Oct 28 '11 at 11:56
Sorry, I'm not sure that I understood you correctly. Graph is an object $(G,E)$ where $G$ stands for vertices (e.g. points on the plain) and $E$ stand for edges (e.g. segments of lines) between vertices. The degree of a vertex is a number of edges which goes out/in this vertex. Given degrees for vertices there may not be a way to draw such graph. – Ilya Oct 28 '11 at 12:02
@Gortaur: I think that susan’s response refers specifically to the set of degrees given in the problem, not to anything more general. In other words, in effect it’s merely a repetition of the original question (and I’m not inclined to go further than Joe Johnson’s hint without some indication of where the difficulty lies, since the first reasonable thing to try works). – Brian M. Scott Oct 28 '11 at 12:10
@BrianM.Scott: thanks for the clarification, maybe that's what susan meant – Ilya Oct 28 '11 at 12:17

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.

-
+1 for the Falcon. Activate tractor beam... – draks ... Aug 18 '13 at 19:38