The idea here is to represent the path Pn with n vertices as an intersection graph. We associate with each vertex a subset of a given set A, where |A| = K, and we require that two vertices are adjacent if and only if the cardinality of the intersection of the corresponding two subsets >= 2. The 2-intersection number of a graph is the smallest cardinality of a set A on which a 2-intersection representation is possible. It is apparently extremely difficult to determine the 2-intersection number of a path! [M.S. Jacobson, A.E. Kezdy and D.B. West, The 2-Intersection Number of Paths and Bounded-Degree Trees, preprint].
Obviously, the problem of finding a longest path in a graph is NP-complete. This is not what Schwenk is asking. Instead, he wants to know if there exists a graph having three longest paths which do not intersect in a common vertex. All graph theorists know the famous result which states that every two longest paths in a connected graph must have a vertex in common. However, Schwenk says that a graph is known in which there exist something like seven longest paths which do not intersect in a common vertex. But no one has ever found a graph with three longest paths having this non-intersecting property.