Problem A. 807. (October 2021)
A. 807. Let \(\displaystyle n \ge 2\) be a given integer. Let \(\displaystyle G\) be a finite simple graph with the property that each of its edges is contained in at most \(\displaystyle n\) cycles. Prove that the chromatic number of the graph is at most \(\displaystyle n+1\).
Proposed by Ádám Schweitzer, Budapest
(7 pont)
Deadline expired on November 10, 2021.
Solution of Lászlo Simon:
Suppose that the statement is not true for some \(\displaystyle n\). Let us consider graph \(\displaystyle G\) with the smallest number of vertices that is a counterexample. Let us establish some important facts about graph \(\displaystyle G\).
\(\displaystyle G\) is a connected graph: indeed, if it is not connected, then there is a connected component that cannot be colored using \(\displaystyle n+1\) colors. Since a circuit is a connected subgraph, the condition about the cycles is satisfied in each component. Each component has a smaller number of vertices than \(\displaystyle G\), which yields a contradiction.
\(\displaystyle G\) is not complete: this statement is really easy to check.
\(\displaystyle G\) is not an odd cycle: an odd cycle can be colored using 3 colors, and \(\displaystyle n+1\ge 3.\)
\(\displaystyle G\) does not contain a cut vertex: suppose on the contrary that removing vertex \(\displaystyle v\) \(\displaystyle G\) decomposes into connected components \(\displaystyle H_1\), \(\displaystyle H_2\),... Now create spanning subgraphs \(\displaystyle G_1\), \(\displaystyle G_2\),... by adding vertex \(\displaystyle v\) to components \(\displaystyle H_i\). Note that graphs \(\displaystyle G_i\) satisfy the condition about the cycles, because cycles are biconnected. Since graphs \(\displaystyle G_i\) have a smaller number of vertices than \(\displaystyle G\), they can be colored using \(\displaystyle n+1\) colors. Now syncing the color of \(\displaystyle v\) in these colorings we get a coloring of \(\displaystyle G\) with \(\displaystyle n+1\) colors, which is a contradiction.
Now using Brooks' theorem we get that \(\displaystyle G\) must contain a vertex with a degree of at least \(\displaystyle n+2\): let's call this vertex \(\displaystyle u\), and \(\displaystyle n+2\) of its neighbors \(\displaystyle u_1\), \(\displaystyle u_2\),..., \(\displaystyle u_{n+2}\). Now we will show that there are at least \(\displaystyle n+1\) cycles containing vertex \(\displaystyle u\). Since \(\displaystyle u\) cannot be a cut vertex, removing \(\displaystyle u\) yields a connected graph \(\displaystyle G'\). Thus we can find a path between \(\displaystyle u_1\) and \(\displaystyle u_k\). Connecting the endpoints of this path, \(\displaystyle u_1\) and \(\displaystyle u_k\) to \(\displaystyle u\) we get a cycle, and thus we get \(\displaystyle n+1\) distinct cycles, which contradicts the condition of the problem.
Statistics:
16 students sent a solution. 7 points: Bán-Szabó Áron, Ben Gillott, Diaconescu Tashi, Kovács 129 Tamás, Kökényesi Márk Péter, Lovas Márton, Móricz Benjámin, Nádor Benedek, Seres-Szabó Márton, Simon László Bence, Sztranyák Gabriella, Varga Boldizsár. 6 points: Molnár-Szabó Vilmos. 5 points: 1 student. 2 points: 1 student. 0 point: 1 student.
Problems in Mathematics of KöMaL, October 2021