# Degree of vertices in planar graph

Here is the problem:

Let $G$ a planar graph with $12$ vertices. Prove that there exist at least $6$ vertices with degree $\leq 7$.

Here it is what I did:

Since $G$ is planar the number of its edges is $m\leq 3n-6=30$.

Assume now that there are only $5$ vertices ($w_1 ,w_2 ,\cdots ,w_5$) with degree $\leq 7$. Then the other $7$ vertices have degree $\geq 8$.

It is $2m= \displaystyle{ \sum_{v \in V(G)} deg(v) \geq \sum_{j=1}^{5} deg(w_j) +7 \cdot 8}$

so it must be $\displaystyle{\sum_{j=1}^{5} deg(w_j) +56 \leq 60}$.

From here I can't do nothing.

• Is there also an assumption that the graph is connected? And, you should be able to do something, such as subtract 56 from both sides of the equation. Feb 1, 2012 at 17:08
• Hint: You can assume $G$ is connected because, if you have a counter-example which is disconnected, you can find a connected counter-example... Feb 1, 2012 at 17:11
• @Graphth:No there in no such assumption. Actually the problems states that in $G$ the number of vertices is $\geq 12$, but I think that if we prove it for a graph with $12$ vertices we are done. Feb 1, 2012 at 17:12
• @ThomasAndrews Ah, yes, good point. Hmm, but what if your counterexample is a disconnected graph of order 12. Then, its connected component that is not planar is order 11 or less. Feb 1, 2012 at 17:14
• No, you can add edges to a disconnected counterexample to make it connected and still (1) planar, and (2) a counterexample. Feb 1, 2012 at 17:19

Let $G$ be a planar graph with $n$ vertices and the minimum number $k$ vertices of degree at most $7$. We may assume that $G$ is maximal, since adding edges doesn't increase the number of "small degree" vertices.

In this case, if $n>3$ there are no vertices of degree two, since a path going through a degree two vertex can't be in two faces bounded by three edges.

From Euler's formula: $$6n - 12 \ge 3k + 8(n - k)$$ or $$5k \ge 2n + 12$$ If $n=12$ we discover $$5k\ge 36$$ and so $$k > 6$$

• Because you take $G$ to be maximal planar the number of edges must be $m=3n-6$. Can you explain a little more this step "In this case, if n>3 there are no vertices of degree two, since a path going through a degree two vertex can't be in two faces bounded by three edges." ? Feb 1, 2012 at 19:26
• The point is that in a maximal planar graph, all the faces are triangles. If $v$ has neighbors as neighbors $a$ and $b$, then the edge $ab$ has to be in $G$. But then the other side of $va$ and $vb$ are in the same face, which then needs to contain a 4th vertex at least. Alternatively, at any vertex, the angles need to sum to $2\pi$, which implies there are at least three triangles incident on any vertex. Feb 1, 2012 at 21:27
• Thank you for your time! I understand it. Very nice solution! Feb 1, 2012 at 23:29

First we show that if we have a counter-example, we can find a counter-example which is connected.

Let $G$ be a planar graph with connected components $G_1$, $G_2$, ..., $G_k$. Select nodes $x_i\in G_i$, and create a new graph $G'$ defined by starting with $G$ and then adding edges $\{x_1,x_2\},\{x_2,x_3\},...,\{x_{k-1},x_k\}$. I'll leave it to you to prove that $G'$ is still planar, and, if $G$ is a counter-example to your theorem, then so is $G'$.

So, you've shown there can be no connected counter-example with $|G|=12$, and hence, by this argument, there can be no counter-example with $|G|=12$.

[Effort to prove via induction elided.] As Graphth noted above, your argument can be used for $n=|G|\geq 12$, too.

$$m\leq 3n-6$$ $$\sum_{x\in G} deg(x) = 2m \leq 6n-12$$ But if $G$ is a connected counter-example, then $\sum_{x\in G} deg(x) \geq 8(n-5) + 5$

So $$8n-35 \leq 6n-12$$ or $$2n\leq 23$$

Note that connectedness is more than you really need, you just need to know that $deg(x)\geq 1$ for all nodes $x\in G$. So it's very easy to take any counter-example to a counter-example where no nodes are isolated because adding an edge from an isolated node to another node does not break the planar nature of the graph.

• Thank's for your answer! If $G'$ wan not planar then it exists $H \subset G'$ which is isomorphic to $K_5$ or to $K_{3,3}$ and $H$ would be also subgraph of $G$ which is absurd since $G$ is supposed to be planar. Also $G'$ is still a counter-example because the degree of the nodes is still the same except the nodes $x_1 , \cdots ,x_k$ whose degree in $G'$ is the degree in $G$ plus 1. Feb 1, 2012 at 18:13
• Sorry but I have one more question. If $G$ is not-connected and $n=|G| \geq 12$ how can I get a contradiction? Feb 1, 2012 at 18:44
• @passenger: See the answer I posted for a more general argument that gets specialized later. Feb 1, 2012 at 19:03
• If $G$ is not connected, then you you proceed by adding the edges as I outlined above to get a connected planar graph $G'$ with $|G'|=|G|$. Then there must be $6$ nodes in $G'$ that have degree $\leq 7$, and hencethere must be $6$ nodes in $G$ that have degree $\leq 7$. Feb 1, 2012 at 19:06
• @ThomasAndrews: Thank's once again! Feb 1, 2012 at 19:16