I have some problems when I prove "For a planar graph $G$ and $\deg(v) = 3$ for any vertex $v$, there is a face with at most $5$ edges". I want to prove with contradiction.
Suppose that every face has more than $5$ edges.
Then $2e > 5r$ ($e$ is the number of edges and $r$ is the number of faces) because each edge occurs on the boundary of a face exactly twice.
Also, I can get $2e = 3v$. (for every edges has $2$ vertices)
So we have $3v > 5r$.
Then, with Euler's formular: $r = e - v + 1$, and $2e = 3r, 3v > 5r$ we can get $r > 20$.
But I cannot lead to a contradiction with the steps above.
Did I miss some points or my idea is not ok? Thanks.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Instead of $2e>5r$, you may get more mileage out of $2e\ge6r$. $\endgroup$– Gerry MyersonJun 10, 2020 at 12:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If $G = (V, E)$ is a planar graph with $|E|\geq g$ and no cycle of length $< g$, then $$e \leq \frac{g}{g − 2}(v − 2)$$. This is a standard generalisation of the result $e \leq 3v-6$ which can be proved easily.
In this problem $g=6$, so we get $e \leq \frac{3}{2}(v-2)$, but since all vertices have degree $3$, number of edges is exactly equal to $\frac{3v}{2}$, hence a contradiction. Hence the graph must have a face with at most 5 edges.
