# Graph theory: Questions about Hamiltonian cycles.

1. Prove that if graph $$G$$ has $$n \geq 2$$ vertices such that the sum of the degrees of $$2$$ different vertices is at least $$n- 2$$, so there are $$2$$ different simple paths ('foreign' to one another) such that the union of both simple paths, builds the original graph (The path can be of length $$0$$ meaning it has only $$1$$ vertex)

2. Calculate how many Hamiltonian cycles there are in $$K_{n,n}$$ ?
Added to 2: Different Hamiltonian cycles* (sorry I did not mention this, I thought it does not matter. My bad!)
My approach:

So I need to prove that there exist 2 trees (?-I am not sure..) $$T_1$$ and a tree $$T_2$$ ($$T_1 \neq T_2$$) such that $$G = T_1 \cup T_2$$ ( Hope I got the question right..) If graph $$G$$ has $$n = 2$$ vertices, and the sum of the degrees is at least $$2-2=0$$ then it is trivial, if $$G$$ consists of $$v_1$$ and $$v_2$$ then $$T_1 = \{v_1\} , T_2 = \{v_2\}$$ and $$G = T_1 \cup T_2$$

I am really stuck from here... I would appreciate your kind help!

1. I know there are $$\frac{1}{2} (n-1)!$$ Hamiltonian cycles in $$K_n$$ but does that really matter the graph is bipartite with $$n,n$$ ? I still think the answer does not change.. and it is $$\frac{1}{2} (n-1)!$$ the problem is that I am completely unsure if this is the answer or how to prove it... I am completely lost...

2)) I assume that a Hamiltonian cycle (see, for instance, “Chromatic Graph Theory” by Chartrand and Zhang) for a graph $$G$$ is a sequence $$v_0,\dots, v_k$$ such that $$k\ge 3$$, $$v_0,\dots, v_{k-1}$$ is a permutation of the vertices of $$G$$, $$v_0=v_k$$, and vertices $$v_{i}$$ and $$v_{i+1}$$ are adjacent for each $$0\le i\le k-1$$. When $$G$$ is $$K_{n,n}$$ then such sequences are exactly the sequences such that $$n\ge 2$$, $$v_0=v_{2n}$$, and sequences $$(v_{2k})_{1\le k\le n}$$ and $$(v_{2k-1})_{1\le k\le n}$$ are permutations of a the bipartition parts of $$K_{n,n}$$. So there are $$n!$$ possibilities for each of such sequences, and, moreover, two possibilities to choose a starting bipartition part. This yields in total $$2n!^2$$ Hamiltonian cycles for $$K_{n,n}$$.
• Thank you for answering! one question, someone told me the TA solved it and the answer is $\frac{(n!)^2}{2n}$ does it sound right? because it is different than what you wrote, does it have to do with duplication ? Thank you! – MathAsker Jul 2 '20 at 11:34
• @StackOMeow I think correctness of the value depends on a definition of a cycle, this is why I cared to look for and refer to an exact definition. According to it, the cycle has a start point and direction. But if we ignore both and consider a cycle as a graph, then we should divide my answer by $2n$ (to ignore different starting vertices) and by $2$ (to ignore different directions), and we obtain $\frac{n!^2}{2n}$. – Alex Ravsky Jul 2 '20 at 14:15
• Thank you sir. One little thing - if we need different hamiltonian cycles, then the answer is $\frac{(n!)^2}{2n}$ but you said $2n$ - to ignore the $2n$ vertices to start from and $2$ to ignore directions (forwards and backwards) - but then the answer would be $\frac{(n!)^2}{4n}$ no? or does one thing include the other ? (like, the starting point includes the direction)? Thank you! – MathAsker Jul 2 '20 at 17:54
• My answer was not $n!^2$ but $2n!^2$. When we divide it by $2n\cdot 2=4n$, we obtain $\frac{n!^2}{2n}$. – Alex Ravsky Jul 2 '20 at 18:03