Proving Planar Triangle-Free Graph Has Vertex with Degree ? 3 – Graph Theory

graph theory

How do you prove that every planar, triangle-free graph (it doesn't contain $K_3$ as a subgraph) has at least one vertex that has a degree of $\leq 3$ ?

Best Answer

The sum over all of the faces of the number of edges of each face is equal to twice the number of edges. Since the graph is triangle free this sum is at least $4F$ (Because every face has at least four edges) where $F$ is the number of faces. Hence $4F\leq 2E\implies F\leq \frac{E}{2}$ now plug this into Euler's formula:

$V-E+F=2\implies V-E+\frac{E}{2}\geq 2 \implies V-2\geq \frac{E}{2}\implies E\leq 2V-2$. Since the sum of the vertices twice the number of edges we obtain it is less than or equal to $4V-2$, so it is strictly less than $4V$, hence there must be a vertex of degree strictly less than $4$ as desired.