Problem A. 848. (March 2023)

A. 848. Let \(\displaystyle G\) be a planar graph, which is also bipartite. Is it always possible to assign a vertex to each face of the graph such that no two faces have the same vertex assigned to them?

Submitted by Dávid Matolcsi, Budapest

(7 pont)

Deadline expired on April 11, 2023.

We will only use the fact that \(\displaystyle G\) contains no triangles (instead of being bipartite).

Let us consider the following bipartite graph: the vertices are the faces and the vertices of \(\displaystyle G\), and an edge connects a vertex if the vertex is contained by the face. We have to find a matching in this graph that contains all the faces of \(\displaystyle G\). Based on Hall's marriage theorem this is possible if and only if choosing \(\displaystyle f\) faces there are at least \(\displaystyle f\) vertices connected to at least one of them. Let's prove this statement.

Let us choose some faces of \(\displaystyle G\), and consider graph \(\displaystyle G'\) defined by their vertices and edges.

Let \(\displaystyle G'\) have \(\displaystyle f>0\) faces, \(\displaystyle e\) edges and \(\displaystyle v\) vertices. Using Euler's theorem \(\displaystyle f-e+v \ge 1\).

Every face of \(\displaystyle G'\) has at least \(\displaystyle 4\) edges, and every edge correspond to at most two faces, thus \(\displaystyle 4f\le 2e\), i.e. \(\displaystyle 2f\le e\).

These imply \(\displaystyle v\ge f+1\), which is what we wanted to prove.

Statistics:

15 students sent a solution.
7 points:	Diaconescu Tashi, Lovas Márton, Nádor Benedek, Németh Márton, Sida Li, Szakács Ábel, Varga Boldizsár, Wiener Anna.
5 points:	1 student.
4 points:	3 students.
0 point:	3 students.

Problems in Mathematics of KöMaL, March 2023