Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# 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