Hello everyone!

Consider the following problems.

Problem A

You are given an undirected simple graph with $$$n$$$ nodes and $$$m$$$ edges. It is guaranteed that the graph has no cycles of length $$$3$$$ (i.e., no triangles). You have to label each edge with a distinct integer in $$$[1, m]$$$, in such a way that there are no monotone cycles of length $$$5$$$ (i.e., when traversing a cycle of length $$$5$$$, the edge labels cannot be increasing).

Problem B

Problem A is actually broken. Prove that there exists a test case such that no labeling exists. The test case can have arbitrarily large $$$n$$$.

Challenge for you

Solve Problem B. Here are some hints.

• If we remove the restriction "the graph cannot have triangles", a sufficiently large complete graph works.

• If we replace "cycles of length $$$5$$$" with "cycles of length $$$4$$$" (or any even length), problem A becomes solvable.

Good luck!