Timeline for Eulerian graphs with prescribed number of edges

5 events

when toggle format	what		by	license	comment
Nov 5, 2015 at 1:27	comment	added	Tony Huynh		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, 2015 at 1:13	comment	added	Brendan McKay		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 4, 2015 at 19:56	answer	added	Tony Huynh		timeline score: 3
Nov 4, 2015 at 19:04	comment	added	Noam D. Elkies		$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, 2015 at 18:02	history	asked	Sergiy Kozerenko	CC BY-SA 3.0