7
$\begingroup$

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.

  • 0
    @passenger The proof should be essentially the same if you say the number of vertices is $\geq 12$. Instead of 7 vertices of degree at least 8, you have $n - 5$, and their degrees sum to something bigger than $8 (n - 5)$ and this, plus the degrees of the others, must be less than or equal to $3n - 6$.2012-02-01

2 Answers 2

5

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.

  • 0
    @ThomasAndrews: Thank's once again!2012-02-01
6

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$

  • 0
    Thank you for your time! I understand it. Very nice solution!2012-02-01