In the above graph, the blue line shows a cycle of length $84$, the remaining edges are
higlihtged in red. In total, the graph has $100$ vertices and $143$ edges.
- Is this the longest cycle in this graph ?
The graph has no hamilton cycle because deleting the vertices $8$ and $20$ splits the
graph into $3$ components. Deleting the vertices $1,5,8,13,20,22,25,37$ splits the
graph into $10$ components, so it contains not even a hamiltonian path.
- How can I get the length of the longest cycle ?
Best Answer
The comments gave many resources for finding the longest cycle in such a graph.
This is (not) the longest cycle in a graph. I will give a counterexample of length 85.
After running the longest cycle algorithm on Mathematica for quite some time, a longest cycle (of length 89) in the graph is as below:
To answer your second question, the length of the longest cycle is also known as the graph circumference. That should give you a keyword to start exploring how one might get such a length. There are many ways to find the longest cycle, one of the simplest is a simple modification from the Hamiltonian cycle algorithm.
This is however an NP-complete problem.
Here is the graph in the adjlist format should anyone wants to verify the above solution.