In this thesis we examine the famous conjecture that every three longest paths in a graph intersect, and add to the classes of graphs for which it is known that this conjecture holds. This conjecture arose from a question asked by Gallai in 1966, the question of whether all of the longest paths in a graph intersect (Gallai's question). In 1969, Walther found a graph in which the longest paths do not all intersect, answering Gallai's question. Since then, many other graphs in which the longest paths do not all intersect have been found. However there are also many classes of graphs for which the longest paths all intersect, such as series-parallel graphs and dually chordal graphs. Finding such classes of graphs is an active area of research and in this thesis we add to these classes of graphs.

We begin by investigating Gallai's question for a speci c class of graphs. A theta graph is a graph consisting of three paths with a pair of common endpoints and no other common vertices. A generalised theta graph is a graph with at least one block that consists of at least three paths with a pair of common endpoints and no other common vertices. We show that for a subclass of generalised theta graphs, all of the longest paths intersect.

Next, we consider the conjecture that every three longest paths of a graph intersect. We prove that, for every graph with n vertices and at most n + 5 edges, every three longest paths intersect.

Finally, we use computational methods to investigate whether all longest paths intersect, or every three longest paths intersect, for several classes of graphs. Two graphs are homeomorphic if each can be obtained from the same graph H by a series of subdivisions. We show that, for every simple connected graph G that is homeomorphic to a simple connected graph with at most 7 vertices, all of the longest paths of G intersect. Additionally, we show that, for every simple connected graph G homeomorphic to a simple connected graph with n vertices, n + 6 edges, and minimum vertex degree 3, all of the longest paths of G intersect. We then show that for every graph with n vertices and at most n + 5 edges, every three longest paths intersect, independently verifying this result. We also present results for several additional classes of graphs with conditions on the blocks, maximum degree of the vertices, and other properties of the graph, showing that every three longest paths intersect or every six longest paths intersect for these graphs.