Route Inspection Problem w/ more than 4 odd vertexes

(edited 11 years ago)

Reply 1

If you have 2 odd vertices, there is 1 pairing.
If you have 4 odd vertices, there are 3 x 1 = 3 pairings (3 ways for one vertex, leaving the two vertices).
If you have 6 odd vertices, there are 5 x 3 x 1 = 15 pairings (5 ways for one vertex, leaving four vertices which will recurse back to the previous line).

Let the number of vertices be 2n and try writing this as a product.

Reply 2

Glutamic Acid

You need to be systematic, looking at (if the vertices are A,B,C,D,E,F): AB + others, AC + others, AD + others, AE + others and AF + others; deleting repetitions when they arise. But finding an individual number of pairings isn't important, it's the general rule in my previous post.

If you have 2n vertices, then there will be $1 \times 3 \times 5 \times ... \times 2n-1$ pairings. Try writing this as a quotient.