# Show that in a planar graph (no triangles) there exists a vertex with degree $\leq 3$

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.

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.
• 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. Commented Mar 28, 2018 at 17:29