• Non ci sono risultati.

# 3 take a two-colorable triangulation of a convex (3k − 3)-gon and assume that the external face is white

N/A
N/A
Protected

Condividi "3 take a two-colorable triangulation of a convex (3k − 3)-gon and assume that the external face is white"

Copied!
1
0
0

Testo completo

(1)

Problem 11298

(American Mathematical Monthly, Vol.114, June-July 2007) Proposed by J. Jonsson and J. Propp (USA).

Show that forn ≥ 3, if a convex n-gon admits a triangulation in which every vertex is incident with an odd number of triangles thenn must be a multiple of 3.

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

A vertex is incident with an odd number of triangles if and only if the degree of the vertex is even.

Hence every vertex is incident with an odd number of triangles if and only if the triangulation, which is a plane graph, is eulerian or in other words its faces can be colored with two colors, say black and white (it is two-colorable).

We first prove by induction that if n is a multiple of 3 then a convex n-gon admits a two-colorable triangulation. For n = 3 it is true, and for n = 3k > 3 take a two-colorable triangulation of a convex (3k − 3)-gon and assume that the external face is white. Then take a triangulated 5-gon with the central triangle white and the other two triangles black and glue together one of the sides of the (3k − 3)-gon and the external side of the white triangle. The final polygon (made it convex) is two-colorable and has (3k − 3) + 5 − 2 = 3k = n vertices.

Now we prove by induction that if n is not a multiple of 3 then a convex n-gon does not admit a two- colorable triangulation. For n = 4 and n = 5 this is evidently true. Let n > 6 be not a multiple of 3 and take a triangulation of a convex n-gon. Assume by contradiction that it is two-colorable and that the external face is white.

We have two cases: all the triangles which are adjacent to the external face are ears or not (an ear of a polygon is a triangle formed by three consecutive vertices). In the first case n is even and after removing all these ears, which are all black, we obtain a two-colorable triangulation of a (n/2)-gon (paint the external face black). This would contradict the inductive hypothesis because 3 < n/2 < n and n/2 is not a multiple of 3.

In the second case, there is a triangle which is adjacent to the external face that is not a ear. This triangle is black and it has two sides that are diagonals. Therefore it splits the n-gon triangulation in two triangulated convex polygons: a n1-gon and a n2-gon with n1+ n2= n + 1 and n1, n2≥3.

The n1-gon plus the black triangle is a two-colorable (n1+ 1)-gon triangulation and the n2-gon plus the black triangle is a two-colorable (n2+ 1)-gon triangulation. Now 3 < n1 + 1 < n and 3 < n2+ 1 < n and by inductive hypothesis they must be multiples of 3. Hence it follows that also n = n1+ n2−1 = (n1+ 1) + (n2+ 1) − 3 is a multiple of 3 and this is a contradiction. 

Riferimenti

Documenti correlati

Before acquiring a well-defined position in society, subjects pass through a period and area of ambiguity − a sort of social limbo which has the features neither of the preceding,

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

It remains to show that the partition exists when n is multiple of 8 and n ≥ 16.. For any non-negative integer x, we have a partition of {1

[r]

Since we are comparing two polynomials, it follows that the identity holds for all x

(American Mathematical Monthly, Vol.118, January 2011). Proposed by Kieren MacMillan (Canada) and Jonathan

[r]

Let α, β, and γ be the angle measures of a non-degenerate triangle.. Let a, b and c be the side lenghts and let s be

For statement (3), observe that any two intersecting directed cycles would have to merge together and then split apart, again contradicting the assumption that f is reduced. The

For instance, it was proved that a finite nilpotent group has modular subgroup lattices if and only if every two of its subgroups are permutable.. The full description of finite

There is a characterization of outerplanar graphs that says a graph is outerplanar if and only if it does not contain a subdivision of the complete graph K 4 or the complete

Then there is a co- ordinatization so that the right and middle associated groups (right and middle nuclei) are equal and contained in the left nucleus (coordinate kernel) of

(10) Notice that corrections of this type also arise in the context of a gravity model with vector- induced spontaneous Lorentz symmetry break- ing (Bertolami &amp; P´aramos,

Measurements of flux density are described for five planets, Mars, Jupiter, Saturn, Uranus, and Neptune, across the six Planck High Frequency Instrument frequency bands (100–857

This difference between West Flemish and German follows, if we assume, as I have argued in chapter 3, that in West Flemish only finite verbs can move to the head of AspP.. Else

The conclusion now fo11ows in the same way as in the proof of theorem

Patients suffering from  cluster headache, a primary headache disorder, also show similar re- sults, with significantly lower rCBF changes during the headache-free period compared

Provide the example of a sequential game in extensive form, with two players and two strategies, with two Nash equilibria, but only one 'perfect subgame equilibrium'.

To construct the other three vectors as requested we need to find a basis of W and orthogonalize it... However in this case the calculations are so easy that it can be

The following result shows that not only is the operator norm limit of a sequence of finite- rank operators compact, but every compact operator can be realized as the operator

• Content needing to be rendered or additional files associated with a CDA document (such as a style sheet) can be included in the exchange package;. • There is no need to change

Therefore, the current research explores training modules used in the activities of a park to verify how students can receive a sustainable education from primary school; whether

Water showed a significant decreasing trend with the altitude probably caused by the increasing of SO 4 with the elevation.. Water DOC, soil TC and soil TN had a similar trend