# Number of hamiltonian cycles in a complete graph

In graph theory, a Hamiltonian cycle is a path in a graph that visits each vertex exactly once and returns to the starting vertex. In this article, we will discuss how to calculate the number of Hamiltonian cycles in a complete graph. A complete graph is a graph where each pair of distinct vertices is connected by an edge.

## Problem Statement

Given a complete graph with n vertices, we want to calculate the number of Hamiltonian cycles in the graph.

Let's consider an example to better understand the problem. Suppose we have a complete graph with 6 vertices:

```    1 -- 2
/ \   |
/   \  |
6 -- 5 -3
\   /  |
\ /   |
4 ---
```

In the above graph, there are multiple Hamiltonian cycles:

• 1-2-3-4-5-6-1
• 1-6-5-4-3-2-1
• 1-5-2-3-4-6-1
• and more...

Our goal is to calculate the total number of Hamiltonian cycles in the graph.

## Algorithm

To calculate the number of Hamiltonian cycles in a complete graph, we can use the following algorithm:

1. Initialize a variable 'count' to 1.
2. Initialize a variable 'i' to n - 1.
3. Calculate the factorial of 'i' and update the 'count' variable by multiplying it with 'i' in each iteration.
4. Divide the 'count' by 2.
5. Print the number of nodes and the calculated number of Hamiltonian cycles.

## Pseudocode

```function hamiltonianCycle(node):
count = 1
i = node - 1
while i > 0:
count = count * i
i = i - 1
print("Number of nodes: ", node)
print("Hamiltonian Cycles: ", count / 2)
```

## Explanation

In the given code, the function 'hamiltonianCycle' takes an input 'node', which represents the number of vertices in the complete graph. It calculates the number of Hamiltonian cycles using the factorial of (node - 1) and then divides it by 2.

The factorial is calculated by starting from 'node - 1' and multiplying it with the previous number in each iteration until reaching 1. For example, if 'node' is 6, the factorial would be 5 * 4 * 3 * 2 * 1 = 120.

Since a Hamiltonian cycle can be traversed in both directions (clockwise and counterclockwise), we divide the calculated count by 2 to get the actual number of unique Hamiltonian cycles.

The code then prints the number of nodes and the calculated number of Hamiltonian cycles for each test case.

## Program Solution

``````// C Program
// Number of hamiltonian cycles in a complete graph
#include <stdio.h>

void hamiltonianCycle(int node)
{
int count = 1;
int i = node - 1;
// Calculate factorial
while (i > 0)
{
count = count *i;
i--;
}
// Display number of nodes
printf("\n Number of node : %d", node);
// Display calculated result
printf("\n hamiltonian Cycle : %d", (count / 2));
}
int main()
{
// Test
hamiltonianCycle(6);
hamiltonianCycle(7);
hamiltonianCycle(4);
return 0;
}``````

#### Output

`````` Number of node : 6
hamiltonian Cycle : 60
Number of node : 7
hamiltonian Cycle : 360
Number of node : 4
hamiltonian Cycle : 3``````
``````// Java Program
// Number of hamiltonian cycles in a complete graph
public class Cycle
{
public void hamiltonianCycle(int node)
{
int count = 1;
int i = node - 1;
// Calculate factorial
while (i > 0)
{
count = count * i;
i--;
}
// Display number of nodes
System.out.print("\n Number of node : " + node);
// Display calculated result
System.out.print("\n hamiltonian Cycle : " + (count / 2));
}
public static void main(String[] args)
{
// Test
}
}``````

#### Output

`````` Number of node : 6
hamiltonian Cycle : 60
Number of node : 7
hamiltonian Cycle : 360
Number of node : 4
hamiltonian Cycle : 3``````
``````// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Number of hamiltonian cycles in a complete graph
class Cycle
{
public: void hamiltonianCycle(int node)
{
int count = 1;
int i = node - 1;
// Calculate factorial
while (i > 0)
{
count = count *i;
i--;
}
// Display number of nodes
cout << "\n Number of node : " << node;
// Display calculated result
cout << "\n hamiltonian Cycle : " << (count / 2);
}
};
int main()
{
// Test
return 0;
}``````

#### Output

`````` Number of node : 6
hamiltonian Cycle : 60
Number of node : 7
hamiltonian Cycle : 360
Number of node : 4
hamiltonian Cycle : 3``````
``````// Include namespace system
using System;
// Csharp Program
// Number of hamiltonian cycles in a complete graph
public class Cycle
{
public void hamiltonianCycle(int node)
{
int count = 1;
int i = node - 1;
// Calculate factorial
while (i > 0)
{
count = count * i;
i--;
}
// Display number of nodes
Console.Write("\n Number of node : " + node);
// Display calculated result
Console.Write("\n hamiltonian Cycle : " + (count / 2));
}
public static void Main(String[] args)
{
// Test
}
}``````

#### Output

`````` Number of node : 6
hamiltonian Cycle : 60
Number of node : 7
hamiltonian Cycle : 360
Number of node : 4
hamiltonian Cycle : 3``````
``````package main
import "fmt"
// Go Program
// Number of hamiltonian cycles in a complete graph

func hamiltonianCycle(node int) {
var count int = 1
var i int = node - 1
// Calculate factorial
for (i > 0) {
count = count * i
i--
}
// Display number of nodes
fmt.Print("\n Number of node : ", node)
// Display calculated result
fmt.Print("\n hamiltonian Cycle : ", (count / 2))
}
func main() {

// Test
hamiltonianCycle(6)
hamiltonianCycle(7)
hamiltonianCycle(4)
}``````

#### Output

`````` Number of node : 6
hamiltonian Cycle : 60
Number of node : 7
hamiltonian Cycle : 360
Number of node : 4
hamiltonian Cycle : 3``````
``````<?php
// Php Program
// Number of hamiltonian cycles in a complete graph
class Cycle
{
public	function hamiltonianCycle(\$node)
{
\$count = 1;
\$i = \$node - 1;
// Calculate factorial
while (\$i > 0)
{
\$count = \$count * \$i;
\$i--;
}
// Display number of nodes
echo("\n Number of node : ".\$node);
// Display calculated result
echo("\n hamiltonian Cycle : ".((int)(\$count / 2)));
}
}

function main()
{
// Test
}
main();``````

#### Output

`````` Number of node : 6
hamiltonian Cycle : 60
Number of node : 7
hamiltonian Cycle : 360
Number of node : 4
hamiltonian Cycle : 3``````
``````// Node JS Program
// Number of hamiltonian cycles in a complete graph
class Cycle
{
hamiltonianCycle(node)
{
var count = 1;
var i = node - 1;
// Calculate factorial
while (i > 0)
{
count = count * i;
i--;
}
// Display number of nodes
process.stdout.write("\n Number of node : " + node);
// Display calculated result
process.stdout.write("\n hamiltonian Cycle : " + (parseInt(count / 2)));
}
}

function main()
{
// Test
}
main();``````

#### Output

`````` Number of node : 6
hamiltonian Cycle : 60
Number of node : 7
hamiltonian Cycle : 360
Number of node : 4
hamiltonian Cycle : 3``````
``````#  Python 3 Program
#  Number of hamiltonian cycles in a complete graph
class Cycle :
def hamiltonianCycle(self, node) :
count = 1
i = node - 1
#  Calculate factorial
while (i > 0) :
count = count * i
i -= 1

#  Display number of nodes
print("\n Number of node : ", node, end = "")
#  Display calculated result
print("\n hamiltonian Cycle : ", (int(count / 2)), end = "")

def main() :
#  Test

if __name__ == "__main__": main()``````

#### Output

`````` Number of node :  6
hamiltonian Cycle :  60
Number of node :  7
hamiltonian Cycle :  360
Number of node :  4
hamiltonian Cycle :  3``````
``````#  Ruby Program
#  Number of hamiltonian cycles in a complete graph
class Cycle
def hamiltonianCycle(node)
count = 1
i = node - 1
#  Calculate factorial
while (i > 0)
count = count * i
i -= 1
end

#  Display number of nodes
print("\n Number of node : ", node)
#  Display calculated result
print("\n hamiltonian Cycle : ", (count / 2))
end

end

def main()
#  Test
end

main()``````

#### Output

`````` Number of node : 6
hamiltonian Cycle : 60
Number of node : 7
hamiltonian Cycle : 360
Number of node : 4
hamiltonian Cycle : 3``````
``````// Scala Program
// Number of hamiltonian cycles in a complete graph
class Cycle()
{
def hamiltonianCycle(node: Int): Unit = {
var count: Int = 1;
var i: Int = node - 1;
// Calculate factorial
while (i > 0)
{
count = count * i;
i -= 1;
}
// Display number of nodes
print("\n Number of node : " + node);
// Display calculated result
print("\n hamiltonian Cycle : " + (count / 2));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Cycle = new Cycle();
// Test
}
}``````

#### Output

`````` Number of node : 6
hamiltonian Cycle : 60
Number of node : 7
hamiltonian Cycle : 360
Number of node : 4
hamiltonian Cycle : 3``````
``````// Swift 4 Program
// Number of hamiltonian cycles in a complete graph
class Cycle
{
func hamiltonianCycle(_ node: Int)
{
var count: Int = 1;
var i: Int = node - 1;
// Calculate factorial
while (i > 0)
{
count = count * i;
i -= 1;
}
// Display number of nodes
print("\n Number of node : ", node, terminator: "");
// Display calculated result
print("\n hamiltonian Cycle : ", (count / 2), terminator: "");
}
}
func main()
{
// Test
}
main();``````

#### Output

`````` Number of node :  6
hamiltonian Cycle :  60
Number of node :  7
hamiltonian Cycle :  360
Number of node :  4
hamiltonian Cycle :  3``````
``````// Kotlin Program
// Number of hamiltonian cycles in a complete graph
class Cycle
{
fun hamiltonianCycle(node: Int): Unit
{
var count: Int = 1;
var i: Int = node - 1;
// Calculate factorial
while (i > 0)
{
count = count * i;
i -= 1;
}
// Display number of nodes
print("\n Number of node : " + node);
// Display calculated result
print("\n hamiltonian Cycle : " + (count / 2));
}
}
fun main(args: Array < String > ): Unit
{
// Test
}``````

#### Output

`````` Number of node : 6
hamiltonian Cycle : 60
Number of node : 7
hamiltonian Cycle : 360
Number of node : 4
hamiltonian Cycle : 3``````

## Output Explanation

The given code is tested with three different test cases: 6, 7, and 4.

For the first test case with 6 nodes, the code calculates the factorial of 5 (6-1) which is 120. Since a complete graph with 6 nodes has 120 different Hamiltonian cycles, dividing it by 2 gives us the output 60.

Similarly, for the second test case with 7 nodes, the code calculates the factorial of 6 (7-1) which is 720. Dividing 720 by 2 gives us the output 360.

For the last test case with 4 nodes, the code calculates the factorial of 3 (4-1) which is 6. Dividing 6 by 2 gives us the output 3.

## Time Complexity

The time complexity of the given algorithm depends on the value of 'node'. Since the factorial is calculated using a loop that iterates from 'node-1' to 1, the time complexity can be considered as O(n) where 'n' is the number of vertices in the complete graph.

As a result, the time complexity of the code is linear, making it efficient for practical purposes even for larger values of 'node'.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.