What is the maximum and minimum length of Eulerian cycle possible in graph on $n$ vertices?

34 Views Asked by At

Consider all graphs on $n$ vertices. What the longest and the shortest Eulerian cycles do they have?

Such question arised recently on StackExchange, but it was deleted eventually, because OP wanted to ask essentially different question. I want to keep my answer available.

1

There are 1 best solutions below

0
On BEST ANSWER

Eulerian cycle is a cycle that contains every edge of a connected graph exactly once. Therefore length of the Eulerian cycle equals to the number of edges in the graph. Thus the question is about minimum and maximum number of edges of Eulerian graph on $n$ vertices.

It is known that a connected graph is Eulerian if and only if the degree of each vertex is even. Since graph is connected it has at least $n - 1$ edges. But connected graph wtih $n - 1$ edges is tree and has a vertex of degree $1$ if $n > 1$, thefore such graph is no Eulerian. So for $n > 1$ Eulerian graph contains at least $n$ edges, and this bound is feasible. A cycle $C_n$ is Eulerian and has $n$ edges.

Vertex degree in a simple graph is at most $n - 1$, so maximum even degree is $2\left\lfloor\frac{n - 1}2\right\rfloor$. If $n$ is odd then the complete graph $K_n$ with $\frac{n(n - 1)}{2} = n\left\lfloor\frac{n - 1}2\right\rfloor$ edges is Eulerian. If $n$ is even then the complete graph $K_n$ has a perfect matching $M$. If we remove edges of $M$ from the graph then vertex degrees become even and graph becomes Eulerian... if it remains being connected. Definitely problem wtih connectivity is actual for $n = 2$ only. And yes, we forgot that there is no cycle $C_2$ and no simple Eulerian graph at all for $n = 2$. But for even $n > 2$ we get an Eulerian graph $K_n - M$ with $\frac{n(n - 2)}{2} = n\left\lfloor\frac{n - 1}2\right\rfloor$ edges.

So the minimum length is $$\begin{cases}0, & n = 1;\\?!, & n = 2 \\ n, & n > 2.\end{cases}$$ And the maximum length is $n\left\lfloor\frac{n - 1}2\right\rfloor$ for $n \ne 2$.