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.

  • 1
    For the second, how about a graph with two vertices and twelve edges connecting them?2012-04-11
  • 1
    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).2012-04-11
  • 0
    @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)2012-04-11
  • 0
    @deinst, I don't understand the First part, to which problem it refers?2012-04-11
  • 0
    From http://en.wikipedia.org/wiki/Planar_graph: From v − e + f = 2 and 3f <= 2e (one face has minimum 3 edges and each edge has maximum two faces) it follows via algebraic tranformations that the average degree is strictly less than 6. Otherwise the given Graph can't be planar. 22 seems quite generous-seems like you should be able to get less than or equal to 12.2012-04-11
  • 0
    @xan It allows you to generate fully triangulated planar graphs2012-04-11
  • 0
    @Ross Millikan, no requested example must be planar, read the text again.. otherwise it would be too easy :)2012-04-11
  • 0
    @Ross Millikan, why 3f <= 2e? I thought there would be equality 3f = 2e..2012-04-11
  • 0
    @xan: right. I don't think you will get there without a multigraph. You just can't have enough edges2012-04-11
  • 6
    "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.2012-04-11
  • 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
    how to show that at least $\frac{3}{4}$ of the vertices are low degree and what does it give me?2012-04-13
  • 0
    @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.2012-04-13
  • 0
    @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..2012-04-13
  • 0
    @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.2012-04-13
  • 0
    @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?2012-04-14
  • 0
    @xan The triangle is not a counterexample. You need to show that the smallest graph for which every edge has total degree greater than 22 has smallest degree at least 4. Show that if you have such a graph with a vertex of degree 3, you can make a smaller graph with the same properties.2012-04-14
  • 0
    I have no idea how to prove that, however. It sounds odd that I'd want to prove that I can be infinitely decreasing the number of edges of a finite graph preserving the degree property and I have no idea how to prove that.2012-04-15
  • 0
    @tqw: If you are the same person as xan, the moderators can merge your accounts for you.2012-04-15
  • 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

  • 0
    How is this a triangulation?2014-05-23
  • 1
    @Servaes: It's not, of course (as stated in the problem, triangulations cannot have such an edge.)2016-02-22