1
$\begingroup$

Consider a complete graph G with n vertices.

Each vertex is indexed by [n] = {1,2,3...n} where n >= 4.

In this case, a Hamiltonian cycle is determined only by the collection of edges it contains, and we do not need to consider its orientation or starting point.


Question:

  1. How many Hamiltonian cycles are there in G?
  2. How many Hamiltonian cycles in G contains the edge {1,2}?
  3. How many Hamiltonian cycles in G contains the edge {1,2} and {2,3}?
  4. How many Hamiltonian cycles in G contains the edge {1,2} and {3,4}?
  5. Suppose that M is a set of k <= (n/2) edges, in which no two edges in M share a vertex. How many Hamiltonian cycles contain all edges in M? Give answer in terms of k and n
  6. How many Hamiltonian cycles in G do not contain the edge {1,2}, {2,3} and {3,4}?

The question really clusters into two parts.

PART 1: How do I discount "orientation" and "starting point"?

This has to do with 1, 2, 3, 4, and 6.

I can calculate the combinations of edges there can be, but that's not what they're asking. They only want the combinations that form a Hamiltonian cycle.

Additionally, I don't see how you can just know whether a Hamiltonian cycle has crossed through a certain edge.

The more I think about it, the more I feel this is about combinatorial numbers as opposed to graph theory. Are they trying to trick me?

PART 2: How many cycles contain a set of edges that do not share a vertex.

This has to do with question 5, specifically.

My first response is "none..."?

If the graph is a complete graph, then all edges share a vertex at some point right? In that case, M seems to be an empty set and there are no Hamiltonian cycles that cover it. But that doesn't feel right at all...

$\endgroup$
1
$\begingroup$

Hint: if we do consider starting point and orientation, then the number of Hamiltonian cycles is the number of ways that we can order $[n]$, i.e. the number of permutations. If you know the order in which to visit the vertices, this tells you exactly the cycle. Each cycle is then counted $n$ times for each possible starting point, and twice for each direction around the cycle.

Hint for part 2: A cycle can contain $\{ 1,2 \}$ and $\{ 3,4 \}$ if it (for example) also contains edge $\{ 2,3 \}$.

$\endgroup$
  • $\begingroup$ Thanks for the hint, here's what I wrote for questions: Q1) n! / 2n, Q2: (n-2)!, Q3: (n-3)! $\endgroup$ – potatoguy Nov 30 '18 at 2:58
  • $\begingroup$ I'm still stuck on Q4, since the graph is separated into two sections. Do you happen to have more advise on how to approach this problem? I'm testing it out on a complete graph K5 (result seems to be 4), but I'm still trying to see how I reach this solution. $\endgroup$ – potatoguy Nov 30 '18 at 3:05
  • $\begingroup$ Well, you could try treating vxs 1 and 2 as a single vx (and same for 3 and 4), then find the number of cycles. But remember both these edges can appear in two directions on a cycle. $\endgroup$ – Puck Rombach Nov 30 '18 at 3:12
0
$\begingroup$

Q(a)-Q(c) is correct, and Q(d) can be seen as {1,2}{2,3}{3,4} - {2,3} which is 2(n-2)!-(n-3)! (e) can brake into (12)(34)(56)789 and applying counting,answer=(n)!(n-k-1)!/(2n) (f)Obviously Answer=1/2(n-1)!-(n-3)!

$\endgroup$

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.