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?
2 Answers
$\begingroup$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.
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!
$\endgroup$ 2
