2
$\begingroup$

In a finite connected planar graph $G$, such that $\delta(G)\geq 3$, show that at least $2$ faces have at most $5$ edges. I have tried writing out degree sum from Handshaking lemma and then substituting in Euler's formula but I am stuck there.

$\endgroup$
2
  • $\begingroup$ Shouldn't it be at least 4 faces? $\endgroup$
    – almagest
    Commented Jan 16, 2020 at 11:42
  • $\begingroup$ No, i just checked the exercise, its says what I wrote in question. $\endgroup$
    – Dovla
    Commented Jan 16, 2020 at 11:53

1 Answer 1

2
$\begingroup$

Using the fact $\delta(G)\geq 3$, one could prove each edge is part of a cycle, and therefore bound exactly two faces.

Denote by $e,v,f$ the number of edges, vertices and faces in $G$ respectively.

Intuition

Since the proof is quite technical, I'll try to sum up the proposition I use:

  1. $(f-1)\leq \frac{e}{3}$
  2. $2e\geq 3v$ which implies $v-\frac{2e}{3}\leq 0$
  3. Euler formula $v-e+f=2$

Proof

Now assume by contradiction the statement is false, and therefore at least $f-1$ of the faces have at least $6$ edges.
This implies: $$2e=\sum\limits_{i=1}^{f} \text{#edges of the face } f_i\geq 6(f-1)\implies \\ 2e\geq 6(f-1)\implies (f-1)\leq \frac{e}{3}$$

Using Euler formula $v-e+f = 2$, we get $$ 2 = v-e+f\leq v-e+\frac{e}{3} +1=v-\frac{2e}{3} + 1$$

Since

$$2e = \sum\limits_{u\in V(G)}deg(u) \geq 3v\implies \frac{2e}{3}\geq v$$

and finaly we get a contradiction: $$v-\frac{2e}{3}\leq 0 \implies v-\frac{2e}{3} + 1 \leq 1$$ and because $$v-e+f \leq v-\frac{2e}{3} + 1 $$ we get
$$2 = v-e+f \leq 1 $$

which is a contradiction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .