Prove that planar graph with girth at least 6 contains a vertex of degree at most 2.

1.3k Views Asked by At

I'm trying to prove that planar graph with girth at least 6 contains a vertex of degree at most 2.

However, I'm not sure how would I do so. Could you please help me?

1

There are 1 best solutions below

0
On BEST ANSWER

By Euler's formula for plane graphs, $$ v+f=e+2.$$ If each vertex has degree $\ge 3$, then $2e\ge 3v$. By the assumption about the girth, each face has at least $6$ edges, so $2e\ge 6f$. Thus $$ 12=6v+6f-6e\le 4e+2e-6e=0,$$ contradiction.