0
$\begingroup$

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.

$\endgroup$
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
    $\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 Mar 28 '18 at 17:29
  • $\begingroup$ Yeah, I always forget that it has to be connected. $\endgroup$ – Aqua Mar 28 '18 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.