[Math] Planar graphs with $n \geq 2$ vertices have at least two vertices whose degree is at most 5

Question

This is a homework problem and my solution. I think I get the main ideas and understand what is going on, but I need to work on my proof writing. I don't get full credit when I think I should get a little better than what I have been getting.

Theorem: For $n \geq 2$, planar graphs with $n$ vertices have at least two vertices whose degree is at most 5.

Proof: Let $G$ be a planar graph. We will do cases, $n=2$ then $n > 2$.

Case 1. For $n=2$, if $G$ is a planar graph with $n$ vertices then either $G$ is the complete graph of order $2$, $K_2$, or $G$ is the null-graph of order $2$, $N_2$. In the former case each vertex has degree 1 and in the latter case each vertex has degree 0 so the condition is satisfied.

Case 2. Suppose $n >2$. We will further assume that $G$ is connected. Then since $G$ is a planar graph, we have
$$e \leq 3n -6$$
where $e$ is the number of edges of $G$.

Assume for contradiction that at most one vertex has degree smaller than or equal to 5.

Suppose there is only one such vertex, $v_k$ where $\mathrm{deg}(v_k)\leq 5$. Then by the handshaking lemma we have
$$2e = \sum_{i=1}^n \mathrm{deg}(x_i) \geq 6(n-1) + \mathrm{deg}(v_k)$$
$$\Rightarrow \mathrm{deg}(v_k) \leq 2e-6n+6 \leq 2(3n-6)-6n+6=-6$$
a contradiction.

Suppose there are no such vertices, then all vertices has degree larger than or equal to 6.

Then,

$$2e = \sum_{i=1}^n \mathrm{deg}(x_i) \geq 6n \Rightarrow e \geq 3n$$
$$\Rightarrow 3n \leq e \leq 3n -6 $$
$$\Rightarrow 0 \leq -6$$
a contradiction.

Suppose that $G$ is disconnected and has connected components $G_1,G_2,…G_m$. If any of the connected components have $n \geq 2$ vertices, the condition is satisfied by above. The other case is they all only have $1$ vertices in which case $G$ is just a null graph and the condition is satisfied.

This is really more of a draft but it has all my ideas.

Thank you very much if you took the time to read this.

Answer 1

Yes your ideas are correct. For the sake of not leaving this question unanswered, I'll refine your proof a bit.

---

Proofs in graph theory have a tendency to naturally be broken into cases like your proof above. A lot of the time though, this isn't necessary, and you can make a proof more concise by trying to combine cases.

For example, in your proof, separating out the case where $n=2$ is not necessary. The inequalities in your $n > 2$ case covers it. In fact explicitly stating a base case is often only necessary when you are arguing by induction. Also separating the cases where there is one vertex of degree at most five and no vertices of degree at most five is not necessary. Since $6n \geq 6(n-1) + \operatorname{deg}(v_k)$, your work for the first cases actually covers both cases.

Theorem: For $n \geq 2$, a planar graph with $n$ vertices must have at least two vertices with degree at most five.

Proof $\;$ First note that if this theorem holds for connected graphs, then it must hold for non-connected graphs as well because we can consider a single component and find the required two vertices with degree at most five.

Let $G$ be a connected planar graph with $n \geq 2$ vertices and $e$ edges. Suppose for the sake of contradiction that $G$ has at most one vertex, call it $v_k$, of degree less than or equal to five. Then by the handshaking lemma we have $$ 2e = \!\!\!\sum_{v_i \in \operatorname{V}(G)}\!\!\!\operatorname{deg}(v_i) \geq 6(n-1) + \operatorname{deg}(v_k) \geq 6n-1\;. $$ But since $G$ is planar and connected we know that $e \leq 3n-6$, getting us the contradiction $$ 6n-1 \;\leq\; 2e \;\leq\; 2(3n-6) = 6n-12\;. $$ Therefore there must be at least two vertices of degree at most five.