## Hamilton Paths in $K_{2n}$

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Hi,

I am teaching this semester graph theory for undergraduate students. Now, I am discussing with them about Hamilton Paths in finite graphs. Last time we meet, I presented the following theorem:

Theorem. For $n\geq 3$ the complete graph $K_n$ is decomposable into edge disjoint Hamilton cycles iff n is odd. For $n\geq 2$ the complete graph $K_n$ is decomposable into edge disjoint Hamiltonian paths iff $n$ is even.

During the class I noted that my argument to prove this theorem was not complete. I started proving that the second statement implies the first one, which is ok. But I had not a correct argument to show that there exist an edge disjoint decomposition of $K_n$ in $n/2$ Hamilton paths if $n$ is even.

Can we explicitly construct such decomposition or just present an existence argument ?

-

## 1 Answer

We can explicitly construct such a decomposition.

Label the vertices of the graph with ${0,1,...,n-1}$, take the first path to be $0, n-1, 1, n-2, 2,... ,n/2$ and generate the other paths by addition modulo $n$ (the $n$ paths come in pairs in which one is the reverse of the other).

More generally, a symmetric sequencing in a group with a single involution is sufficient to construct the decomposition.

-

Thank you Matt.  – Leandro  Apr 6 2011 at 23:51
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 13, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.916242241859436, "perplexity_flag": "head"}