1
$\begingroup$

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!

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks Brian! I drew it out and I see what you mean. Before I was focusing on making it work instead of drawing something that satisfied the conditions of being simple and of also have two vertices with degree 5. Thanks for the swift response! $\endgroup$
    – King Tut
    Commented Feb 20, 2016 at 20:59
  • $\begingroup$ @KingTut: You’re welcome! $\endgroup$ Commented Feb 20, 2016 at 21:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .