0
$\begingroup$

  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...
Improve this question
$\endgroup$
1
$\begingroup$

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}$.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – MathAsker Jul 2 '20 at 11:34
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Alex Ravsky Jul 2 '20 at 14:15
  • 1
    $\begingroup$ 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! $\endgroup$ – MathAsker Jul 2 '20 at 17:54
  • 1
    $\begingroup$ My answer was not $n!^2$ but $2n!^2$. When we divide it by $2n\cdot 2=4n$, we obtain $\frac{n!^2}{2n}$. $\endgroup$ – Alex Ravsky Jul 2 '20 at 18:03
  • 1
    $\begingroup$ Thank you so much!! $\endgroup$ – MathAsker Jul 2 '20 at 18:05

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.