CODEWITHSUNDEEP
algorithmgraphdiscrete-mathematicshamiltonian-cycle
PrometheusWithoutMind
PrometheusWithoutMind

Reputation: 15

What is the total number of Hamiltonian circuits in a complete undirected graph when one or more edges must always be included?

For a complete undirected graph G where the vertices are indexed by [n] = {1,2,3,...,n} where n >= 4. I am aware that the total number of Hamiltonian Circuits in G is (n-1)! / 2

  1. If we must traverse the edge {1,2}, how many Hamiltonian Circuits are there?
  2. How about if multiple consecutive edges, e.g. {1,2} {2,3} must be traversed?
  3. What if multiple non consecutive edges, e.g. {1,2} {3,4} must be traversed?

Intuitively, for part 1, the answer seems to be (n-2)! /2 but I am not completely sure. For the other parts, I am completely stumped.

Any help is much appreciated!

Upvotes: -2

Views: 236

Answers (1)

juvian
juvian

Reputation: 16068

1) Subcase of 2

2) Consider G' = G - {v1, v2, v3...vk} (the vertexes in the order of appearance in the consecutive edges E you need to use). For every Hamiltonian Circuit C in G', you can add the sequence of edges to any part of C, resulting with C[0..i] + {C[i], v1} + E + {vk, C[i]} + C[i..n].

For graph G', there are (n - 1 - k)! / 2 Hamiltonian Circuits. For each of those circuits, you can extend it between any 2 pairs of consecutive edges like we discussed above. This is, |C| ways of doing it. So the answer would be (n - 1 - k)! / 2 * |C| = (n - 1 - k)! / 2 * (n - k).

You would still need to prove that we are counting all of them this way, and that we are not counting duplicates.

3) A generalization of 2. You count the Hamiltonian Circuits without any vertex mentioned in E, and then start adding 1 by 1 the edges that must be traversed.

Upvotes: 0

Related Questions