Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 .

share|improve this question
3  
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
3  
@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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer
    
+1 for the Falcon. Activate tractor beam... –  draks ... Aug 18 '13 at 19:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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