I am attempting to solve the following problem. I have to draw a graph having the given properties or explain why no such graph exists.
The conditions I am given are that it is a simple graph; with six vertices having degrees 1, 2, 3, 4, 5, 5.
Now I drew this out and saw that a graph with such conditions is only possible if it is not simple i.e. if we can have parallel edges and loops.
Specifically however I am wondering about the given explanation in my book as to why this isn't true. They say:
"Suppose that there is such a graph with vertices a, b, c, d, e, f . Suppose that the degrees of a and b are 5. Since the graph is simple, the degrees of c, d, e, and f are each at least 2; thus there is no such graph."
Specifically I am wondering how the condition of being a simple graph allows one to automatically conclude that each degree must be at least 2.
Thanks!
Best Answer
If $G$ is simple and $\deg a=5$, then $a$ must be joined by an edge to each of the five vertices $b,c,d,e$, and $f$: it can’t have an edge to itself (a loop) or more than one edge to any of the other five vertices. Similarly, $b$ must be joined by an edge to each of the five vertices $a,c,d,e$, and $f$. That means that each of the vertices $c,d,e$, and $f$ is joined by an edge to $a$ and also by an edge to $b$ and therefore must have degree at least $2$.