1
$\begingroup$

Let $G$ be a planar graph with no triangles and $m\geq 2$ edges and $f$ faces. Show that $G$ contains a vertex with degree $\leq 3$.

In a previous exercise, I showed that $f\leq m/2$. I tried proving this by induction on the number of edges. Say we remove an edge $\{u,v\}$. Then if either $u$ or $v$ has degree $<3$, we know that $G$ has a vertex with degree $3$. But I’m not really sure how to proceed, and what to do with the fact that there are no triangles.

$\endgroup$

1 Answer 1

2
$\begingroup$

Suppose $d_i\geq 4$ for each $i$. Then by handshake lemma we have $2m\geq 4n$ where $n$ is a number of vertices.

Now using the fact (you proved) $f\leq m/2$ and Euler formula for planar graphs

$$ 2+m =n+f \leq m/2+m/2 =m$$ we get a contradiction.

$\endgroup$
2
  • 2
    $\begingroup$ Great, thanks! I would like to add, that in the case $G$ is not connected, we should use an induction argument (because we can't use the Euler formula). Then for each component, it would hold that there exists a vertex with degree $\leq 3$, so it would hold for $G$ as well. $\endgroup$
    – Sha Vuklia
    Commented Mar 28, 2018 at 17:29
  • $\begingroup$ Yeah, I always forget that it has to be connected. $\endgroup$
    – nonuser
    Commented Mar 28, 2018 at 18:05

You must log in to answer this question.

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