11
$\begingroup$

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.

  • 0
    @deinst, I thought about this a little. The way I see it: $v-e+f=2$, and I think $3f=2e$, so $e=3v-6$. As Ross Millikan said it seems that average degree is less than 6 because $\sum_{v\in V[G]}\deg(v)=2e$. But I don't know if it gives me something. I don't know what to do next. Vertices $\deg(v)+\deg(u)\le 22$ must be on the same edge and I don't know how to find them. Can you help me?2012-04-13

2 Answers 2

2

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.

  • 0
    I can't give up like that :-) how about proof by contradiction? I thought that when we suppose there exists a triangulation such that in every edge $\left\{v,w\right\}$ there is \deg(v)+\deg(w)>22 we can achieve that this graph can't be planar or triangulation (too many edges).. knowing that average degree is strictly less than $6$ and that in graph from contradiction we have \sum_{ \left\{v,w\right\}\in E[G] }\deg(v)+\deg(w)>22m can't we deduce something? that average degree have to be $\ge 6$ and contradiction?2012-04-17
2

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

  • 1
    @Servaes: It's not, of course (as stated in the problem, triangulations cannot have such an edge.)2016-02-22