# Problem B. 4938. (February 2018)

**B. 4938.** It is known that it is possible to draw the complete graph with \(\displaystyle 7\) vertices on the surface of a torus (see the Császár polyhedron, for example). 7 points are marked on the side of a mug. We want to connect each pair of points with a curve, so that the curves have no interior points in common. What minimum number of these curves need to lead across the handle of the mug?

(6 pont)

**Deadline expired on March 12, 2018.**

**Solution (outline).** In the first part we show that at least 6 edges must be lead through the handle; in the second part we provide a possible drawing of the graph in such a way that exactly 6 edges are drawn on the handle.

**I.** If we remove the handle from the mug and all curves on the handle, the body of the mug is homeomorphic with the sphere, so the 7 points with the remaining curves, considered as edges, form a planar graph. It is well-known that a planar graph with \(\displaystyle n\ge3\) vertices canot have more than \(\displaystyle 3n-6\) edges; our graph has \(\displaystyle n=7\) edges, so the number of remaining curves on the body of the mug is at most \(\displaystyle 3\cdot7-6=15\). The complete graph with 7 vertices has \(\displaystyle \binom72=21\) edges, so at least 6 edges must be lead through the handle.

**II.** The left-hand picture shows a usual drawing of the complete graph with 7 vertices on the torus. Bonding the left and right-hand sides of the rectangle we obtain a pipe; bonding the two ends of the pipe (the upper and lower sides of the rectangle) through the handle we obtain a drawing of the graph, with exactly 6 edges on the handle, as shown in the right-hand picture.

**Selected constructions from students' solutions**

sent by Bence Hervay

sent by Máté Soós

From the ideas of Gábor Pituk

(The opposite sides of the hexagon are bonded together; the handle is the closed curve formed by the red and the orange sides.)

sent by Attila Gáspár

### Statistics:

30 students sent a solution. 6 points: Döbröntei Dávid Bence, Gáspár Attila, Hegedűs Dániel, Hervay Bence, Kerekes Anna, Nagy Nándor, Schifferer András, Schrettner Jakab, Soós 314 Máté, Szabó 417 Dávid. 5 points: Füredi Erik Benjámin. 4 points: 6 students. 3 points: 3 students. 2 points: 3 students. 0 point: 7 students.

Problems in Mathematics of KöMaL, February 2018