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$ – Graphth Feb 1 '12 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$ – Thomas Andrews Feb 1 '12 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 '12 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$ – Graphth Feb 1 '12 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$ – Thomas Andrews Feb 1 '12 at 17:19

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 '12 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 '12 at 18:44
  • $\begingroup$ @passenger: See the answer I posted for a more general argument that gets specialized later. $\endgroup$ – Louis Feb 1 '12 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$ – Thomas Andrews Feb 1 '12 at 19:06
  • $\begingroup$ @ThomasAndrews: Thank's once again! $\endgroup$ – passenger Feb 1 '12 at 19:16

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 '12 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 '12 at 21:27
  • $\begingroup$ Thank you for your time! I understand it. Very nice solution! $\endgroup$ – passenger Feb 1 '12 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.