# 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. In a previous exercise, I showed that $f\leq m/2$. Now I’m asked to show that $G$ contains a vertex with degree $\leq 3$. 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. – Sha Vuklia Mar 28 '18 at 17:29