In this thesis, we investigate the conjecture that every set of three longest paths of a connected graph intersect. In particular, we examine this conjecture for the class of polyhedral graphs.

First, we review when sets of longest paths of a connected graph intersect. We explore the literature regarding the classes of graphs in which sets of longest paths have been proved to intersect.

Then, we outline the core properties of polyhedral graphs, and discuss their construction and minimality. We examine the history of finding non-Hamiltonian polyhedral graphs, and briefly explore the enumeration of small non-Hamiltonian polyhedral graphs.

Next, we present a series of properties of a counterexample to the conjecture that every set of three longest paths of a polyhedral graph intersect. We examine the viability of a minimality argument in the approach to this conjecture, and state three known configurations which are forbidden in a counterexample.

We then present a novel forbidden configuration in a 3-connected counterexample, with at most 20 vertices, to the conjecture that every set of three longest paths of a connected graph intersect. Finally, we use this result to prove that there are no 3-connected graphs with at most 20 vertices in the space of minimal counterexamples to this conjecture.