## Do three longest paths share a vertex?

November 29, 2009 by agnisarma

One of the reasons I find graph theory so interesting is that one can ask so basic and fundamental questions that are extremely difficult to answer. Here is one such problem.

It is easy to see that any pair of maximum length paths in a connected graph should share a vertex. Otherwise, we can get a longer path contradicting the maximality. The natural question that arises is what can we say about three longest paths? What about maximal paths? Do all of them share a vertex?

Zamfirescu and Skupien show that for this need not be the case.

Balister, Gyori, Lehel and Schelp show that for interval graphs and circular arc graphs, all paths do have non-empty intersection.

Recently, Maria Axenovich shows that any 3 longest paths in outerplanar graphs have a common vertex.

It would be interesting to look at planar graphs now that outerplanar graphs are known.

### Like this:

Like Loading...

## Leave a Reply