# Hard planar graph problem

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.

• For the second, how about a graph with two vertices and twelve edges connecting them? – Ross Millikan Apr 11 '12 at 17:23
• First, If you have a face with more than three edges, then you can draw an edge between two non adjacent vertices of that face until no face has more than three vertices. Second, consider eulers formula. If each face has three edges and three vertices and each edge bounds two faces, what can you say about the degrees of the verrices. (some fiddling will be necessary to get the bound). – deinst Apr 11 '12 at 17:26
• @Ross Millikan, it will be ok. But what about graphs that are not multi graphs (there is no ban for multi graphs in the text but I find it more interesting) – xan Apr 11 '12 at 17:36
• @deinst, I don't understand the First part, to which problem it refers? – xan Apr 11 '12 at 17:37
• "however in school we hadn't very difficult things. We had four color theorem...", that is definitely not my impression of the four-color theorem. – utdiscant Apr 11 '12 at 18:08

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.

• how to show that at least $\frac{3}{4}$ of the vertices are low degree and what does it give me? – xan Apr 13 '12 at 18:38
• @xan Can you show that a minimal triangulated example has minimum degree $\le 4$? If you can do that, then knowing that the average degree is less than 6 gives you that at least $\frac{3}{4}$ of the vertices have low degree. – deinst Apr 13 '12 at 19:25
• @deinst, I'm little confused.. Perce wrote that I must show a minimum triangulated counterexample has minimum degree $\ge 4$, and you wrote that I must show that a minimal triangulated example has minimum degree $\le 4$. That's two different case's I think. I don't know what to do. Besides I don't know why this implies that low degree vertices are $\frac{3}{4}$ of all vertices.. – xan Apr 13 '12 at 22:31
• @xan I mistyped. Sorry. If all the vertices are of degree at least 4 and the average degree is less than 6, then at least 3/4 of the vertices have degree less than 12. – deinst Apr 13 '12 at 23:41
• @deinst, I'm terribly sorry but I just don't know where does it come from. I have a feeling that you are trying to explain me something completely trivial and I can't understand it :( Besides, the smallest triangulation is a triangle I think. Each of two faces are bounded by three edges (so triangle) and for all vertices there is $\deg(v)=2$. Where am I wrong? – xan Apr 14 '12 at 9:32

Example of planar graph without vertex of degree equal to 1, which doesn't have such edge:

Graph with 23 vertices, in which two vertices we distinguish. Two distinguished vertices have degree of 21, the rest have degree of 2 and every vertex have edges to both of distinguished vertices.

And then every edge on one end have vertex with degree of 2, on the second end with degree of 21. 21 + 2 > 22

• How is this a triangulation? – Servaes May 23 '14 at 15:23
• @Servaes: It's not, of course (as stated in the problem, triangulations cannot have such an edge.) – Kundor Feb 22 '16 at 1:00