Pancyclic graph

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

An n-vertex graph G is pancyclic if, for every k in the range 3 ≤ k ≤ n, G contains a cycle of length k. It is node-pancyclic or vertex-pancyclic if, for every vertex v and every k in the same range, it contains a cycle of length k that contains v. Similarly, it is edge-pancyclic if, for every edge e and every k in the same range, it contains a cycle of length k that contains e.

A bipartite graph cannot be pancyclic, because it does not contain any odd-length cycles, but it is said to be bipancyclic if it contains cycles of all even lengths from 4 to n.

A maximal outerplanar graph is a graph formed by a simple polygon in the plane by triangulating its interior. Every maximal outerplanar graph is pancyclic, as can be shown by induction. The outer face of the graph is an n-vertex cycle, and removing any triangle connected to the rest of the graph by only one edge (a leaf of the tree that forms the dual graph of the triangulation) forms a maximal outerplanar graph on one fewer vertex, that by induction has cycles of all the remaining lengths. With more care in choosing which triangle to remove, the same argument shows more strongly that every maximal outerplanar graph is node-pancyclic. The same holds for graphs that have a maximal outerplanar spanning subgraph, as do for instance the wheel graphs.

...
Wikipedia