*Graph Drawing*book by Di Battista, Eades, Tamassia, and Tollis, pp. 75–76. Every 3-connected graph has a peripheral cycle, and every 2-connected graph with minimum degree three has a peripheral cycle. So how hard is it to find a peripheral cycle, if one exists, in an arbitrary graph?

The answer turns out to be that it's NP-complete. The proof I found uses two reductions, one from graph three-coloring to a problem of finding cycles with forbidden pairs of vertices, and a second one from that to finding peripheral cycles.

**( Read more...Collapse )**

## Error

Your reply will be screened

Your IP address will be recorded