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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|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|cite|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.