Let $G=(V,E)$ be a graph with $|V|=6,|E|=10$. Prove there exists vertex $v$ such that $\deg v=4$ or $\deg v=5$- Possible pigeonhole solution?

Question

I know it's a very basic question both in graph theory and discrete math but unfortunately it's kind of had for me to wrap my head around this one.

Let $G=(V,E)$ be a simple graph with $|V|=6,|E|=10$. Prove there exists vertex $v$ such that $\deg v=4$ or $\deg v=5$.

I managed to prove it using contradiction and the fact that $\sum_{v\in V}\deg(v)=2|E|$ and Of course I'm fine with this proof but the first thing I thought about when I saw this problem is solving using the pigeonhole principle- but couldn't do it.

Some thoughts I had before resorting to proof by contradiction were: There can be only one vertex $v$ such that $\deg v=0$ because for any number $<5$ even the complete graph won't have enough edges. And if there exists such vertex then we have $5$ vertices left to connect and then the number of edges in the complete graph with $5$ edges is $\binom{5}{2}=10$ and the number of edges is $10$ so every vertex would have a degree of 4 and we're done. So we can assume that for any $v\in V$ we have $0<\deg v<6$. Not sure it helps though!

So my question is: Is there a way to prove this claim using pigeonhole principle? Is the proof I wrote some how equivalent to the pigeonhole principle?

Sorry if it's too basic, and thanks for any help!

Answer 1

Assuming that the graph is simple, sure. There are $20$ half-edges in the graph and $6$ vertices, so the Pigeonhole Principle says that there have to be a vertex with $\lfloor20/6\rfloor+1=4$ half-edges.

Answer 2

So you have 6 vertices and 10 edges. Suppose there is no one of degree 4 or 5, then all are od the degree 3 or less, so we have, by Handshake lemma: $$20 =2|E|= \sum _{i=1}^6 d_i \leq 6\cdot 3 = 18$$ a contradiction.