Can someone help me with the prove of the following statement:

We have an array of numbers: $J=\{0,1,2,...,n\}$. Those numbers form unordered pairs with the following rules:

  • For each number there is a pair such that both members are the number ($\{1,1\},\{2,2\}$).
  • For each two numbers there is a pair that contains them.
  • Each pair of numbers is unique.

Basically we have combinations with repetition.

We need to prove that we can order those pairs in such a way that they form a circle (the last and the first pair are next to each other) in such a way that every number from a pair is the same as the number from the neighboring pair only when $J$ contains odd number of values.

Example of an order that satisfies the rules: $\{1,2\}\{2,3\}\{3,1\}$.

  • $\begingroup$ As far as I see, the statement is not correct, because you could have $\{1,2\}, \{2,3\}, \{1,3\}$ and you can't form a circle with that. $\endgroup$ – 5xum Jul 12 '17 at 7:25
  • $\begingroup$ he said unordered pairs. But still, I am a bit confused from the question $\endgroup$ – TStancek Jul 12 '17 at 7:30

This is basically asking if you can play a set of double-$n$ dominoes in a single big loop, right?

You can't do it if $|J|=n+1$ is even. This is because each number must appear the same number of times as the first element of a pair that it appears as the second element of the pair (because every time it appears as the first element, it was the second element of the (cyclically) previous pair). So each number must appear an even number of times. But each number appears $n+2$ times (twice in the "double" pair and then in $n$ other pairs), so we need $n+2$ to be even, i.e. $|J|$ is odd.

The question doesn't seem to ask you to prove the converse too, but the fact that you can do it if $|J|$ is odd follows from the fact that a connected graph with all degrees even is Eulerian.


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.