1
$\begingroup$

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

$\endgroup$
3
  • 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$ Nov 4 '15 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$ Nov 5 '15 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 Huynh
    Nov 5 '15 at 1:27
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.