How to prove that this simple graph does not exist?

Question

Show that there is no simple graph with 6 vertices in which there are 5 vertices having following degrees 5,5,3,2,1

So, we have 5 vertices (=odd number of vertices) with an even number of degrees. Why? Because 5+5+3+2+1 = 16. We don't know the sixth one, so I do this:

[5,5,3,2,1,n] where n = unknown. We already know that the rest is 16 and I drew this graph, and I get a graph where one vertex is connected to another vertex twice (so it has two edges between vertex x and y)...

Now, I know that from the definition of a simple graph, that it is impossible as a simple graph does not allows us to have two edges between two vertices.

My question: am I correct and is this "enough" to "proof" this, or should I calculate something? I mean, could I even calculate this with Havel-Hakimi for example? If so, could someone show me that?

Answer 1

Suppose it's possible. We have 6 vertices with these degrees:

Let's add the edges starting from the largest-degree vertices. We pick one of the degree-5 vertices: since there are only 5 other vertices, it must be adjacent to all of them.

Now let's do the next degree-5 vertex. It likewise must be adjacent to all other vertices.

A clash arises. The degree-1 vertex has degree greater than 1, giving a contradiction.

---

The main observation is that:

• In an $n$-vertex simple graph, vertices of degree $n-1$ are adjacent to all other vertices.

So consequently:

• If we have $k$ vertices of degree $n-1$ in a $n$-vertex simple graph, every other vertex must have degree $k$ or more.

Answer 2

You have two vertices $P_1$ and $P_2$ each adjacent to all other vertices. You also have a third vertex $P_3$ of valency one. But $P_3$ is adjacent to $P_1$ and $P_2$. Ouch!