Triangulation is called a planar graph in which every face is a triangle.
$\bullet$ Prove that in every triangulation exists edge $\left\{ u,v \right\}$ such that $\deg(u)+\deg(v)\le 22$.
$\bullet$ Give an example of planar graph without vertex of degree equal to $1$, which doesn't have such edge.
It seems to be very hard (and strange limit: $22$), however in school we hadn't very difficult things. We had four color theorem, Euler characteristic, Kuratowski's theorem, in short – all classic. But this problem.. I don't even know how to start and even imagine an example of graph that I should give in second part of this problem.
I can't even imagine an example of triangulation.. I assume that even unbounded face should be a triangle. I just don't see.
Best Answer
Hint:
Call vertices of degree $< 12$ low degree and other vertices high degree. We want to find an edge adjacent to two low degree vertices.
First show that a minimum triangulated counterexample has minimum degree $\geq 4$. Second, show that at least $\frac{3}{4}$ of the vertices are low degree. Last, find the number of edges in the graph.