Problem 1832

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 \geq 4(p + 1 - m)$, which gives $p \leq \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 $VA_i$, $A_iB_i$, $B_iC_i$, $C_iV$, 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 \leq \frac{4(2t-1)}{3}$ for $t \geq 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$.