Question on Planar Graph ($\deg(v) = 3$ and $\deg(f) ≤ 5$ or $\deg(v) ≤ 5$ and $\deg(f) = 3$)

Question

I am stuck with this question. Any help is appreciated.

Let the minimum degree of a plane graph $G$ be at least $3.$ Prove that there are a face $f$ and a vertex $v ∈ f$ such that either $\deg(v) = 3$ and $\deg(f) ≤ 5$ or $\deg(v) ≤ 5$ and $\deg(f) = 3$.

I am aware of the Euler formula and a few conditions regarding edges when there is no $3$-cycle. and I think these condition should suffice for solving the mentioned numerical but I am not still able to make any progress.

Answer 1

You will have to assume that $G$ is finite; otherwise the graphs of the regular tilings are counterexamples.

There is a "trick" to it, which once you've seen you'll probably remember. Basically we take multiples of Euler's formula and replace the edge term with various combinations of vertex degrees and face degrees.

Let $v_i$ be the number of vertices of degree $i$, $f_j$ the number of faces of degree $j$, and $e$ the number of edges. Then $$ 2e = \sum_{i \geq 3} i \, v_i \\ 2e = \sum_{j \geq 3} j \, f_j $$

Adding these equations together, we can get $$ 4e = \sum_{i \geq 3} i\, v_i + \sum_{j \geq 3} j\, f_j, $$ and substitute it into four times Euler's formula $4v - 4e + 4f = 8$: $$ \sum_{i \geq 3} 4 v_i - \sum_{i \geq 3} i\, v_i - \sum_{j \geq 3} j\, f_j + \sum_{j \geq 3} 4 f_j = 8 $$ or $$ \sum_{i \geq 3} (4 - i) v_i + \sum_{j \geq 3} (4 - j) f_j = 8. $$ The only positive contributions on the left hand side come from either vertices or faces of degree 3, so we see there must be at least eight elements of degree 3.

Similar rearrangements using $$ 6e = \sum_{i \geq 3} 2 i\, v_i + \sum_{j \geq 3} j\, f_j $$ into six times Euler's formula gives $$ 2 \sum_{i \geq 3} (3 - i) v_i + \sum_{j \geq 3} (6 - j) f_j = 12. $$ This shows that some faces have degree $j \leq 5$ (otherwise the LHS would be zero or negative.)

And using $6e = \sum_{i \geq 3} i\, v_i + \sum_{j \geq 3} 2 j\, f_j$ will show some vertices have degree $i \leq 5$.

Answer 2

Let $E$ be number of edges and $f_i$ indicate faces, $v_i$ vertices.
$2E= \sum_i deg(f_i)$
$2E= \sum_i deg(v_i)$ \

Assume:

Let $deg(f_i) \leq 5$, then let the vertices in the face $f_i$ are such that $deg(v) > 3$. $\sum_i deg(f_i) \geq 6 f + 3 g $ where $f $ is the number of faces of degree $>5$, $g$ is the number of faces of degree $\leq 5$.

Since its a planar graph: $|V|-|E|+|F|= 2 \leq |V|-(6 f+ 3g)/2 + f + g = |V| -2 f - 0.5 g$.

Hence $2 f + 0.5 g \leq |V|-2$. \

By similar argument u will get: Hence $2 U + 0.5 W \leq |F|-2$. where $U$ is the number of vertices of degree $>5$ and $W$ is the number of vertices of degree $\leq 5$

So we have :

1. $2f+0.5g \leq U+W-2$
2. $2U+0.5W \leq f+g-2$ \

1)+2) => $2f+0.5g+2U+0.5W \leq V+W-2+f+g-2$
$f-0.5g+U-0.5W \leq -4$
$f+U \leq (g+W)/2-4$\

Also we have $|V| \leq 2|E|/3$ (since $deg(v_i) \geq 3$).

Hence $|V|-|E|+|F|= 2 \leq -|E|/3+|F| \leq -(6f+3g)/6+f+g = g/2$. Hence $g \geq 4$. Similarly we have $W \geq 4$. Using this lower bound on $g$: $2f+0.5g\leq |V|-2$ => $2f\leq |V|-4=U+W-4$. Similalrly we have $2U \leq |F|-4= f+g-4$ So we have: \begin{equation} f+U \leq (g+W)/2-4 \\ 4 \leq g, 4 \leq W \\ f \leq (U+W)/2-2 \\ U \leq (f+g)/2-2 \\ \end{equation} This seems like a general inequality. Not sure how to proceed. Will think more. Currently giving this as a hint.