# Eulerian graphs with prescribed number of edges

Under what conditions there exists an $n$-vertex eulerian graph with $m$ edges for $1\leq m\leq\frac{n(n-1)}{2}$?

• $m$ must be at least $3$; if $n-1$ is even then $\frac{n(n-1)}{2} - m$ is either $0$ or at least $3$; if $n-1$ is odd then $m$ is at most $\frac{n(n-2)}{2}$. These easy necessary conditions are probably sufficient too. Nov 4 '15 at 19:04
• If "eulerian" is intended to include being connected, as it often does, then the condition $m\ge n$ needs to be added to Noam's conditions. It is slightly delicate when $m$ is only slightly greater than $n$, but it seems ok. Nov 5 '15 at 1:13
• Yes, adding $m \geq n$ is sufficient for connectivity. For $m=n$, we can take a Hamiltonian cycle. For $m=n+1$ we can take two cycles that meet at one vertex and span the whole graph. For $m=n+2$ we can take three cycles that meet at a vertex and span the whole graph. For $m \geq n+3$, we can apply the result in my answer where we insist that one of the cycles in the decomposition is a Hamiltonian cycle (which guarantees connectivity). Nov 5 '15 at 1:27

The characterization given by Noam Elkies is correct. Indeed, in this paper Bryant, Horsley and Pettersson prove the stronger result that if $n$ is odd, and $m_1, \dots, m_t$ are such that $3 \leq m_i \leq n$ for each $i$ and $\sum_{i=1}^tm_i=\binom{n}{2}$, then the edges of $K_n$ can be decomposed into $t$ cycles with specified lengths $m_1, \dots, m_t$. If $n$ is even, and $m_1, \dots, m_t$ are such that $3 \leq m_i \leq n$ for each $i$ and $\sum_{i=1}^tm_i=\binom{n}{2}-\frac{n}{2}$, then $E(K_n)$ can be decomposed into a perfect matching and $t$ cycles with specified lengths $m_1, \dots, m_t$.