Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
Thanks a lot! Is there a place where "Eulerian trail is 0 or 2 verticles with odd degree and the rest has even degree" is proven in a rather simple way? Once again, many thanks! – Studentmath Feb 27 '14 at 19:26
@Studentmath You are welcome! Do you have access to textbooks? It should be a standard theorem in one of the chapters. – Yong Hao Ng Feb 27 '14 at 19:31
I will look out for it in Douglas B. West's book, cheers once again! – Studentmath Feb 27 '14 at 19:33
@Studentmath No problem, you can ping me in chat if you would like to talk to me. =D – Yong Hao Ng Feb 27 '14 at 19:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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