-
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)
-
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!
- 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…
Best Answer
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}$.