Under what conditions there exists an $n$-vertex eulerian graph with $m$ edges for $1\leq m\leq\frac{n(n-1)}{2}$?
$\begingroup$
$\endgroup$
3
asked Nov 4, 2015 at 18:02
-
3$\begingroup$ $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. $\endgroup$– Noam D. ElkiesCommented Nov 4, 2015 at 19:04
-
2$\begingroup$ 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. $\endgroup$– Brendan McKayCommented Nov 5, 2015 at 1:13
-
$\begingroup$ 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). $\endgroup$– Tony HuynhCommented Nov 5, 2015 at 1:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
answered Nov 4, 2015 at 19:56