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.

  • $\begingroup$ 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. $\endgroup$
    – GeoffDS
    Feb 1, 2012 at 17:08
  • 2
    $\begingroup$ Hint: You can assume $G$ is connected because, if you have a counter-example which is disconnected, you can find a connected counter-example... $\endgroup$ Feb 1, 2012 at 17:11
  • $\begingroup$ @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. $\endgroup$
    – passenger
    Feb 1, 2012 at 17:12
  • $\begingroup$ @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. $\endgroup$
    – GeoffDS
    Feb 1, 2012 at 17:14
  • 1
    $\begingroup$ No, you can add edges to a disconnected counterexample to make it connected and still (1) planar, and (2) a counterexample. $\endgroup$ Feb 1, 2012 at 17:19

2 Answers 2


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$$

  • $\begingroup$ 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." ? $\endgroup$
    – passenger
    Feb 1, 2012 at 19:26
  • $\begingroup$ 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. $\endgroup$
    – Louis
    Feb 1, 2012 at 21:27
  • $\begingroup$ Thank you for your time! I understand it. Very nice solution! $\endgroup$
    – passenger
    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.

  • $\begingroup$ 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. $\endgroup$
    – passenger
    Feb 1, 2012 at 18:13
  • $\begingroup$ Sorry but I have one more question. If $G$ is not-connected and $n=|G| \geq 12$ how can I get a contradiction? $\endgroup$
    – passenger
    Feb 1, 2012 at 18:44
  • $\begingroup$ @passenger: See the answer I posted for a more general argument that gets specialized later. $\endgroup$
    – Louis
    Feb 1, 2012 at 19:03
  • $\begingroup$ 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$. $\endgroup$ Feb 1, 2012 at 19:06
  • $\begingroup$ @ThomasAndrews: Thank's once again! $\endgroup$
    – passenger
    Feb 1, 2012 at 19:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .