# Show that a graph G cannot exist with vertices of the given degree

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

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

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?

-
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?

-

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.

-

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