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.

I'm working through the book titled Introductory Graph Theory by Gary Chartrand. There is a question that I can't figure out. The question is:

Show that a graph G cannot exist with vertices of degree 1, 3, 3 and 3.

I can show it with a picture, but would like to formalize it with a proof.

Thanks

share|improve this question
    
Such a graph can certainly exist. You need to put some conditions on it. –  TonyK Jun 23 '11 at 15:36

4 Answers 4

up vote 6 down vote accepted

If the graph has no loops or multiple edges, and such a graph existed, what would be involved after one removes the 1-valent vertex and the edge attached to it?

share|improve this answer
    
I'm sorry I'm not following your response. This is only chapter two and I've had no previous exposure to this subject. I'm trying to teach myself, so go easy on me :) –  gortloveslinux Jun 23 '11 at 15:42
    
@gortloveslinux: Rephrased, take out the vertex with degree 1, and examine how the degrees of the other vertices would change. Is such a structure possible? –  Michael Chen Jun 23 '11 at 15:45
    
Thanks Michael for the clarification. –  gortloveslinux Jun 23 '11 at 16:12

Another way of thinking about it is that each of the vertices of degree three must be adjacent to every other vertex (again assuming no loops or multiple edges). What does that say about the degree of the remaining vertex?

share|improve this answer

Another way of thinking about it (no loops or multiple edges) is to see that the graph must be a subgraph of the complete graph on four vertices. This has six edges and the one you want will have five (sum the degrees and divide by two). Try to construct the graph by removing an edge. When you take an edge away from that graph you affect two vertices out of the four ...

This shows also that there is only one type of graph with four vertices and five edges. Building up from zero edges does not make that obvious.

share|improve this answer

You can prove this in a formal, straightforward way by means of the Havel-Hakimi Algorithm:

  1. Order the degree sequence in non-increasing order: 3,3,3,1.
  2. Remove the leftmost element, 3, and decrement the next 3 elements by 1 to obtain the sequence 2,2,0. Repeating this process, we obtain the sequence 1,-1 which is obviously not graphical.
  3. Since the sequence 1,-1 is not graphical, by the Havel-Hakimi Theorem, the original sequence 3,3,3,1 is not either graphical.
share|improve this answer

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.