# For which values of n does G have an eulerian trail

The question is as follows:

Let $n\ge3$ be a natural number. Let $G=(V,E)$ where $V=\{1,2,3,\dotsc,2n\}$ and $E=\{\{i,j\}:|i-j| \in \{3,5\}\}$.

1. Prove that $G$ is bipartite.
2. For which values of $n$ is $G$ connected?
3. For which values of $n$ does $G$ have an Eulerian trail?

I figured out 1. by 'splitting' $V$ into the two disjoint sets of even and odd numbers, each being an independent set. For 2., I proved via induction that it is true for every $n\ge4$, yet not for $n=3$ (it has two components then). My issue lies with 3.

I know that $G$ is eulerian if and only if it has at most one nontrivial component and its vertices all have even degrees - that is true only when $n=4$. However, that does not necessarily tells me that $G$ has an Eulerian trail only for when $n=4$, or does it? I do not know how to approach it further than that, any hints or suggestions will be extremely appreciated!

-
If $n=4$, from the description then the only edge would be $\{1,4\}$. Then $G$ is not connected? – Yong Hao Ng Feb 27 '14 at 18:49
When n=4, V={1,2,3,...,2n}={1,2,3,...,8}, you can then get the path 1,4,7,2,5,8,3. V goes from 1 to 2n, not from 1 to n. – Studentmath Feb 27 '14 at 18:56
Oh that's right I thought that it meant $\{1,2,3,4\}$. Got it. – Yong Hao Ng Feb 27 '14 at 18:59
I think you meant $4,5,2n-4,2n-3$ has odd degrees (instead of $2n-3,2n-2$, since $2n-2$ has even degrees). That is right. So for $n\geq 5$, these 4 elements are distinct and therefore there cannot be an Eulerian trail. So what you said is right. For $n=4$ they merge into $2$ so you have the Eulerian trail. You have listed one of them: $1,4,7,2,5,8,3$. For $n=3$ the graph is not connected so it does not matter. – Yong Hao Ng Feb 28 '14 at 4:15
So you are done: Eulerian trail if and only if $n=4$. – Yong Hao Ng Feb 28 '14 at 4:22

Hint: For Eulerian trail, $G$ must be connected. Therefore it must satisfy (2).
The condition for Eulerian trail is $0$ or $2$ vertices with odd degree and the rest has even degree. Your goal is to count the degrees for any given $n$.
Consider the case where $n$ is large first and focus on the left half. How many edges do each of them have? More importantly, how many of them can have odd edges? Suppose 0 or 1 of them has odd degree. Is there an Eulerian trail? Can there be 2 vertices with odd edges?
Then finish with the smaller $n$ cases.