3
$\begingroup$

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

  • 0
    Such a graph can certainly exist. You need to put some conditions on it.2011-06-23

4 Answers 4

7

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?

  • 0
    @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?2011-06-23
5

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?

4

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.

1

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.