IMAR Mathematical Competition

Let $G$ be a connected graph with vertex set $V$ and edge set $E$; $G$ may have loops and/or multiple edges. The idea is to expand at most $|V|-1$ suitable edges to pairs of edges to make $G$ into a graph $\hat{G}$ on $V$ each vertex of which has an even degree. A maximal loop in $\hat{G}$ tracing each edge at most once is then Eulerian, i.e., traces each edge exactly once (Euler). Read back in $G$, i.e., identifying each cloned edge back to the original, this is the desired loop: it traces every cloned edge twice, every other edge once, and its length does not exceed $|V| - 1 + |E|$.

To obtain $\hat{G}$, consider a spanning tree $T$ of $G$, i.e., a minimal connected subgraph on $V$. We will show that $T$ has a subgraph $S$ on $V$ such that $\deg_S$ and $\deg_G$ agree modulo 2 at all vertices; clearly, the number of edges of $S$ does not exceed the number of edges of $T$ which is $|V| - 1$. Cloning each edge of $S$ once, while keeping its end points fixed, of course, yields the desired additional edges in $\hat{G}$.

To obtain $S$ from $T$, notice that the sums $\sum_{v \in V} \deg_T v = 2|E_T|$ and $\sum_{v \in V} \deg_G v = 2|E|$ have like parities, to infer that $\deg_T$ and $\deg_G$ disagree modulo 2 at an even number of vertices (possibly zero), say, $v_1, \dots, v_n, v_{n+1}, \dots, v_{2n}$. For each index $i$ in the range 1 through $n$, let $\alpha_i$ be the unique path in $T$ joining $v_i$ and $v_{i+n}$, and collect together all edges of $T$ lying along an even number of the $\alpha_i$ (zero, inclusive) to form the edge set of $S$.

Finally, we show that $\deg_S$ and $\deg_G$ agree modulo 2 at all vertices. To this end, fix a vertex $v$, and let $E'$ be the set of all edges of $T$ having an end point at $v$. For each edge $e$ in $E'$ and each path $\alpha_i$, consider their edge-path incidence number
$$\langle e, \alpha_i \rangle = \begin{cases} 1, & \text{if } \alpha_i \text{ traces } e, \\ 0, & \text{otherwise,} \end{cases} \quad \text{and let } \equiv \text{ denote congruence modulo 2 to write}$$
$$\begin{aligned} \deg_T v - \deg_S v &\equiv \sum_{e \in E'} \sum_{i=1}^n \langle e, \alpha_i \rangle = \sum_{i=1}^n \sum_{e \in E'} \langle e, \alpha_i \rangle \\ &\equiv \begin{cases} 1, & \text{if } v \text{ is a } v_i, \\ 0, & \text{otherwise,} \end{cases} \\ &\equiv \deg_G v - \deg_T v, \end{aligned}$$
on account of $\sum_{e \in E'} \langle e, \alpha_i \rangle$ being congruent to 1 modulo 2 if and only if $\alpha_i$ has an end point at $v$, which is the case if and only if $v$ is one of $v_i, v_{i+n}$. Consequently, $\deg_S v \equiv \deg_G v$ and the conclusion follows.