2
$\begingroup$

I found the following question in a previously assigned graph theory final:

Let $G$ be a simple, planar graph with $1\leq |E(G)|< 30$. Show that $G$ has a vertex with degree at most 4.

My Attempt: this is equivalent to showing $\delta(G)\leq4$. Assume by contradiction that $\delta(G)\geq 5$. First, we know

$5|V(G)|\leq \sum_{v\in V(G)} \text{deg}(v) \leq 2|E(G)|.$

Also, since $G$ is planar we must have

$|E(G)|\leq 3|V(G)|-6,$

which implies

$\frac{5}{2}|V(G)|\leq|E(G)|\leq 3|V(G)|-6.$

From here I am lost. Are there any suggestions for how to continue, or is this not leading to a solution?

1 Answers 1

3

Using the fact that $|E(G)| < 30$ gives $\frac{5}{2} |V(G)| < 30$ or $|V(G)| < 12$.

Using the fact that $\frac{5}{2} |V(G)| \leq 3 |V(G)| - 6$ implies $|V(G)| \geq 12$.

Finished.

And here's a picture of a graph with exactly 30 edges that is planar and 5-regular.

https://math.stackexchange.com/a/162418/8671

  • 0
    you are right, I wrote it down incorrectly.2012-09-21