Claim: Every simple planar graph with minimum degree at least three has an edge $uv$ such that $\deg(u) + \deg(v)\leq 13$. Furthermore, there exists an example showing that $13$ cannot be replaced by $12$.

This seems related to Hard planar graph problem.

By Euler's formula, we know that $|V|-|E|+|F|=2$. Rearranging, we have $|F| = 2+|E|-|V|$

As $\delta\geq3$ we know $|V|\geq 4$ and $|E|\geq 6$ and since each face has at least 3 edges bounding it and each edge is on the boundary of at most 2 faces we have then that $3|F|\leq 2|E|$. Substituting into Euler's formula, we have $$2|E|\geq 3|F| = 3(2+|E|-|V|)\Rightarrow 3|V|-6\geq |E|$$

From this we have from the handshaking lemma that avgdegree = $\sum\frac{\deg(v)}{|V|} = 2\frac{|E|}{|V|} \leq 6 - \frac{12}{|V|}\lneq 6$. And so, the average degree of a simple planar graph is strictly less than 6.

Suppose there was a smallest counterexample, I.e., some graph such that every edge $uv$ has $\deg(u)+\deg(v)>13\dots$

It is at this point that I feel as though I am stuck. It seems that you should be able to reach a contradiction about either the average degree, the planarity, or $\delta\geq 3$. In the hint in the linked similar problem, they suggest to show that you can find a stricter bound for the minimum degree of the smallest counterexample from below, but it doesn't seem to apply here. They then suggest to show that a substantial proportion of the vertices are of low degree (in this problem would translate to degree less than 6), and then for the punchline to show that the number of edges is enough that there are more than #of vertices of high degree choose 2, meaning there must necessarily be an edge between two vertices of low degree thus proving the claim.


2 Answers 2


The discharge method works here. (You can forget this proof, but try to remember the method. It can be very powerful. It belongs in your toolbox next to the pigeonhole principle and the principle of induction).

Assume $G$ is a counterexample with a minimum number of vertices ($n$). We may also assume that we have maximized the number of edges ($e$). So $G$ has minimum degree at least three and $d(u)+d(v)>13$ for every edge $uv$. The edge maximization implies that if there are any non-adjacent $u$ and $v$ with $d(u)+d(v)>13$, then $G+uv$ is not planar.

Now we assign a charge to each vertex: a vertex $v$ gets charge $6-d(v)$. Applying the formula $e\leq 3n-6$ (equality only holds for triangulations), we find the total charge $\sum_v(6-d(v))=6n-2e\geq6n-(6n-12)=12$.

Now we discharge: a vertex $v$ with a positive charge distributes its charge evenly among its neighbours. We do this for all vertices simultaneously.

Since no charge is lost, there must still be vertices with a positive charge.

Let $v$ be a vertex with a positive charge.

Case 1: $d(v)\leq 8$. Since a vertex can only obtain a positive charge from a neighboring vertex $u$ with degree at most 5, we find an edge $uv$ with $d(u)+d(v)\leq 13$. Contradiction.

Case 2: $d(v)=9$. $v$ has no neighbours of degree 3 or 4, so its positive charge can only be obtained from neighbours of degree 5 and each of them contributes a charge of $\frac 15$ (they started with charge 1 and sent an equal part, i.e. $\frac 15$ to each of their neighbours). Since $v$ started out with charge $-3$ it would need 16 neighbours to end up with a positive charge. Contradiction.

Case 3: $d(v)=10$. As case 2: no neighbours of degree 3, and each neighbour of degree 4 or 5 contributes at most charge $\frac 12$. Since $v$ started with charge $-4$, it needs at least 9 neighbours of degree 4 or 5. Let $v_1,\ldots,v_{10}$ be the neighbours of $v$, arranged clockwise. Without loss of generality we may assume that $v_{10}$ is the only vertex that (possibly) has a degree larger than 5. Since $v_1$ and $v_2$ cannot be adjacent (since $d(v_1)+d(v_2)\leq10$), the face containing $v,v_1,v_2$ contains at least one other neighbour $u$ of $v_1$. The degree of $u$ must be at least 9 (or $d(v_1)+d(u)\leq13$). If $u$ is not adjacent to $v$, we can add edge $uv$, contradicting the edge-maximality. So $u$ is another neighbor of $v$, which implies $u=v_{10}$. We have shown that $v_1$ is adjacent to $v_{10}$. Exactly the same argument shows that $v_2,\ldots,v_9$ are adjacent to $v_{10}$. Now consider the adjacent "4-gons" $vv_2uv_1$ and $vv_2uv_3$. Since $d(v_2)\geq4$, $v_2$ must have neighbours that are inside one of these 4-gons, and not neighbours of $v$. Without loss of generality we may assume that $v_2$ has clockwise neighbours $w_0=v,w_1,\ldots,w_t,w_{t+1}=v_2$ where $t\geq1$ and $w_1,\ldots,w_t$ are inside $vv_2uv_1$. Since $d(w_1)\geq3$ we can now add edge $vw_1$ and again contradict edge-maximality.

Case 4: $d(v)\geq11$. Each neighbour of degree <6 contributes at most 1. $v$ starts with charge $6-d(v)$, so it needs at least $d(v)-5$ neighbours of degree less than 6 to end up with a positive charge. Since $d(v)-5>\frac{d(v)}2$ we again must find two consecutive neighbours of low degree and, like in case 3, these must either be adjacent or expose a high-degree neighbour that can be connected to $v$ without breaking planarity. This final contradiction finishes the proof.

For the counterexample we can repeat the same arguments and find that there must be at least 12 vertices of degree 10, each of them surrounded by 5 vertices of degree 3.

This immediately brings up the idea of the icosahedron and indeed, if you take the icosahedron, and add a vertex in the center of each triangle face and connect it to the three corners, you get a very symmetric planar graph with 20 vertices of degree 3 and 12 of degree 10. No two vertices of degree 3 are adjacent, so this is our desired counterexample.

Edit to add: a stellated icosahedron:

enter image description here

  • 1
    $\begingroup$ This is truly an interesting method, one which I had not seen and will read further on. I understand the arguments made in the middle of the proof, however I am still hesitant at the beginning. Would you mind elaborating on why it is we may assume that our counterexample is a triangulation? It seems to me that although indeed by adding edges it can only increase degrees, that we might inadvertently create an adjacency with the desired property that might not have otherwise existed. $\endgroup$
    – JMoravitz
    Commented Dec 18, 2014 at 15:19
  • $\begingroup$ I am afraid you are right. At least you have your counterexample and a partial proof. I will try to find a way to fix it, but that will not be today (Dutch time). $\endgroup$ Commented Dec 18, 2014 at 16:00
  • $\begingroup$ It is no rush. This problem was only for extra practice and for my own understanding. Even without fixing the proof it highlighted a useful proof technique that I will try to keep available for future use and your response was incredibly helpful in that regard. $\endgroup$
    – JMoravitz
    Commented Dec 18, 2014 at 16:04
  • $\begingroup$ @JMoravitz: fortunately it was fixable without affecting the flavor of the proof. $\endgroup$ Commented Dec 19, 2014 at 5:09
  • 2
    $\begingroup$ A stellated icosahedron, what a perfectly delightful result. $\endgroup$
    – Joffan
    Commented Apr 30, 2015 at 22:22

This may be better as a simple comment, but I lack the reputation.

It can be assumed that we are working with a triangulation, but we need to be careful about which edges we add when triangulating. Suppose that the graph has minimum degree three and there is no edge $uv$ with $\deg(u) + \deg(v) \leq 13$. Now suppose there were a face of degree at least four. Let $x$ be the vertex of minimum degree on that face. In any case, both neighbours of $x$ on the face will have degree at least $7$. Add an edge between those two vertices and continue this process until you are left with only triangular faces.

I stole this trick from https://faculty.math.illinois.edu/~west/pubs/dischnew.pdf where it is used at the start of Lemma 3.2. Incidentally, that lemma proves something stronger than what is required here: Every plane graph with minimum degree $3$ has an edge with weight at most $11$ or a $4$-cycle through two degree $3$ vertices and a common neighbour of degree at most $10$.


You must log in to answer this question.

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