Balkan Mathematical Olympiad Shortlisted Problems

We will prove the answer to be $4\cdot 333=1332$. First we prove that a good graph with $n$ vertices has at most $\frac{4(n-1)}{3}$ edges.

Claim 1. If we have 3 paths going from vertex $A$ to vertex $B$, then 2 of them have a common vertex different from $A$, $B$. Proof. Suppose not. By the Pigeonhole principle, observe that 2 of them have the same color attributed to $A$'s edge in them. But if they have no other common points than $A$ and $B$, they form a cycle where the 2 edges next to $A$ have the same color, contradiction. □

Claim 2. No edge lies in more than 1 cycle. Proof. Suppose edge $XY$ lies in cycle $C_1$ and cycle $C_2$. If $C_1$ and $C_2$ have no common vertices except $X$ and $Y$, observe that we can get from $X$ to $Y$ from 3 disjoint paths: on $C_1$, on $C_2$ and directly on edge $XY$, contradicting Claim 1. Thus, $C_1$ and $C_2$ have other common vertices. We can walk on $C_2$ going in the direction from $Y$ to $X$ and suppose $V$ is the first such vertex we encounter. Then we have 3 disjoint paths from $X$ to $V$: this path we just walked from $X$ to $V$ on $C_2$, and the 2 paths given by $C_1$, and all are disjoint by the way we chose $V$, again contradicting Claim 1. □



Consider a connected and good graph with $m$ vertices and $p$ edges. It has a spanning tree containing $m-1$ edges, and every other edge then lies in a cycle where all other edges are edges of the tree, so no 2 such cycles coincide. However, by Claim 2, no two cycles share an edge, and from the statement, all have even lengths, thus at least 4. Furthermore, we have $p+1-m$ such cycles, so we have at least $4(p+1-m)$ edges. This means $p\ge 4(p+1-m)$, which gives $p\le \frac{4(m-1)}{3}$. Now that we've proven the result for connected graphs, all we need to do for non-connected ones is to just apply it for all connected components and sum it up, yielding the result. We are left with providing the example for 1000 vertices: We have a vertex $V$ and 333 triplets $(A_i,B_i,C_i)$ with edges $V{A}_i$, $A_i{B}_i$, $B_i{C}_i$, $C_{i}V$, which can be colored alternatively. This is easily seen to work as these are the only cycles.

We will prove by mathematical induction that $\lfloor \frac{4(n-1)}{3}\rfloor$ is the maximum number of edges for any $n$. We can check the base cases for $n=1,2,3$ by hand. Assume the claim holds for all integers smaller than $n$. Suppose that the claim does not hold for $n$. Since the number of edges is larger than $n-1$ the graph contains a cycle. The cycle has to be of even length, as the consecutive edges must be of different colors. If 2 non-consecutive vertices of a cycle are connected, 2 additional cycles would exist, and it is clear that at least one of these would contain consecutive edges of the same color. Similarly, if there exists a path between 2 vertices belonging to the cycle using only edges that are not on the cycle, 2 additional cycles would exist, and one of them would have consecutive edges of the same color. Notice that if we replace the cycle by a vertex connected to a vertex outside the cycle if and only if one of the vertices in the cycle is connected to it, the condition would be true for the new graph. Let $2t$ be the length of the cycle. Since the new graph has $n-2t+1$ edges, by induction we know that it has at most $\lfloor \frac{4(n-2t+1-1)}{3}\rfloor$ edges. Our original graph thus has at most $\lfloor \frac{4(n-2t+1-1)}{3}\rfloor +2t$ edges. Since $2t\le \frac{4(2t-1)}{3}$ for $t\ge 2$ we get that the graph has at most $\lfloor \frac{4(n-1)}{3}\rfloor$ which is contradiction, so the claim holds for $n$.