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 ${\mathrm{deg}}_S$ and ${\mathrm{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}{\mathrm{deg}}_{T}v=2|E_T|$ and ${\sum }_{v\in V}{\mathrm{deg}}_{G}v=2|E|$ have like parities, to infer that ${\mathrm{deg}}_T$ and ${\mathrm{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 ${\mathrm{deg}}_S$ and ${\mathrm{deg}}_G$ agree modulo 2 at all vertices. To this end, fix a vertex $v$, and let $E^{\prime }$ be the set of all edges of $T$ having an end point at $v$. For each edge $e$ in $E^{\prime }$ and each path ${\alpha }_i$, consider their edge-path incidence number $$⟨e,{\alpha }_i⟩=\{\begin{array}{ll}1,& \text{if }{\alpha }_i\text{ traces }e,\\ 0,& \text{otherwise,}\end{array}\text{and let }\equiv \text{ denote congruence modulo 2 to write}$$ $$\begin{array}{rl}{\mathrm{deg}}_{T}v-{\mathrm{deg}}_{S}v& \equiv \sum _{e\in E^{\prime }}\sum _{i=1}^n⟨e,{\alpha }_i⟩=\sum _{i=1}^n\sum _{e\in E^{\prime }}⟨e,{\alpha }_i⟩\\ & \equiv \{\begin{array}{ll}1,& \text{if }v\text{ is a }{v}_i,\\ 0,& \text{otherwise,}\end{array}\\ & \equiv {\mathrm{deg}}_{G}v-{\mathrm{deg}}_{T}v,\end{array}$$ on account of ${\sum }_{e\in E^{\prime }}⟨e,{\alpha }_i⟩$ 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, ${\mathrm{deg}}_{S}v\equiv {\mathrm{deg}}_{G}v$ and the conclusion follows.