I'm writing a lecture on 5-coloring planar graphs and I'm having trouble visualizing this inequality form the proof
"$2n_5 \leq \sum_{d \geq 12} dn_d$"
I want to make a simple drawing of this concept
Do you know a good way to visualize this? (preferably compatible with latex)
Lemma:
Let G be a planar graph in which every vertex has a degree of at least 5. Then there exists a vertex with degree 5 that has two neighbors, not connected to each other, with degrees $\leq$ 11.
Proof:
It suffices to show that in G there exists a vertex v with degree 5 that has at most one neighbor with a degree greater than 11, because the graph induced by v and any four of its neighbors cannot be a complete 5-vertex graph.
Let $n_d$ denote the number of vertices in the graph with degree d, m the number of edges, and n the total number of vertices.
Since:
$2m = \sum_{d \geq 5} dn_d$
and
$m \leq 3n - 6 = 3 \left( \sum_{d \geq 5} n_d\right)-6$,
We have:
$6 \left( \sum_{d \geq 5} n_d\right)-12 \geq \sum_{d \geq 5} dn_d$
From this, we get:
$6n_5 + 6n_6 + 6 \left( \sum_{d \geq 7} n_d\right)-12 \geq 5n_5 + 6n_6 + \sum_{d \geq 7} dn_d$
Eventually:
$n_5 \geq \sum_{d \geq 7} (d-6)n_d +12$
Assume that every vertex with degree 5 has at least two neighbors with degrees greater than 11.
Then:
$2n_5 \leq \sum_{d \geq 12} dn_d$
From the previous inequalities, we get:
$\sum_{d \geq 7}(2d - 12)n_d + 24 \leq 2n_5 \leq \sum_{d \geq 12} dn_d$
Therefore:
$\sum_{d \geq 7}(2d - 12)n_d + 24 \leq \sum_{d \geq 12} dn_d$
We obtain:
$\sum_{7 \geq d \geq 11}(2d - 12)n_d + \sum_{d \geq 12}(2d - 12)n_d + 24-\sum_{d \geq 12} dn_d \leq 0$
Finally:
$\sum_{7 \geq d \geq 11}(2d - 12)n_d + \sum_{d \geq 12} (d-12) n_d + 24 \leq 0$
Both sums can minimally achieve the value of 0, while the entire left-hand side of the inequality has a value of 24, which is a contradiction, thus completing the proof.
