# Problem 45382. Find a Hamiltonian Cycle in a Graph

You are given a graph g and asked to find a Hamiltonian cycle of g.

See MATLAB graph documentation for details of the graph data structure.

A cycle of g is a sequence of vertices of g such that each adjacent pair of vertices in the sequence share an edge in g and the first and last vertices in the sequence share an edge in g. A Hamiltonian cycle of g is a cycle of g that visits each vertex of g exactly once.

For example, consider the adjacency matrix below.

```A = [
0     0     0     1     1     0     1     1
0     1     0     1     0     0     1     0
0     0     0     1     1     0     0     1
1     1     1     1     0     1     0     1
1     0     1     0     0     1     0     1
0     0     0     1     1     0     0     1
1     1     0     0     0     0     0     0
1     0     1     1     1     1     0     0];
```

This corresponds to the graph with vertices labeled 1 through 8 and an edge between two vertices i and j if and only if A(i, j) == 1. This graph has cycles of vertices [3 4 8], [3 8 1 4], and [5 1 4 3 8], among others. Try the commands below to visualize this.

```g  = graph(A);
gh = plot(g);
```

A Hamiltonian cycle for this graph g is [1 5 6 8 3 4 2 7].

For another fun challenge, see: Restricted Addition

### Solution Stats

40.0% Correct | 60.0% Incorrect
Last Solution submitted on Mar 19, 2023

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!