2
$\begingroup$

Do all longest paths share a common point? (Gallai 1966)

A few years later, Walther produced a counterexample on 25 vertices (a). The simplest counterexample was found by both Walther and Zamfirescu independently and has 12 vertices (b).

Counterexamples

I found this examples in numerous study, but i couldn't find a vertex that does not appear in all longest paths.

Could you explain how should i see these graphs? Where are paths which intersection are empty?

$\endgroup$
  • 1
    $\begingroup$ It might be that the intersection of any two longest paths is non-empty, but the intersection of all longest paths is empty. For comparison, a similar phenomenon for sets is exhibited by $\{1,2\},\{1,3\},\{2,3\}$. (More generally, look up Helly's theorem.) $\endgroup$ – Yuval Filmus Apr 17 '18 at 8:48
  • $\begingroup$ I tried to collect every longest path in graph (Figure b) and i didn't realise, that these paths have empty intersection. Could i prove this theorem by graphically (brute force) on this graph? $\endgroup$ – landorid Apr 17 '18 at 9:01
  • $\begingroup$ See pages 18-19 of Zamfirescu's paper: mscand.dk/article/view/11630/9646. $\endgroup$ – Yuval Filmus Apr 17 '18 at 9:06
  • 1
    $\begingroup$ The graph (b) is obtained from the Petersen graph by taking one of the vertices and separating it into three vertex, one per incoming edge. The crucial property you have to use is that the Petersen graph is that it has a hamiltonian path but no hamiltonian cycle; but if you remove any vertex, then the resulting graph does have a hamiltonian cycle. $\endgroup$ – Yuval Filmus Apr 17 '18 at 9:14
6
$\begingroup$

You need not find a vertex that does not appear in all longest paths (in fact you can't). This is neither sufficient nor necessary. It is sufficient to prove that for each vertex $v$, there exists a longest path that does not contain $v$.

Easy to see the length of the longest path is 10. For convenience, let's encode the vertices as follows.

     1
     2
    3 4
   5   6
  7 8 9 10
11        12

Then for vertices 1,2,7,11,10,12, for example, 1, there is a longest path 11-7-8-4-6-5-3-9-10-12 that does not contain 1.

For vertices 3,4,5,6,8,9, for example, 3, there is a longest path 1-2-4-6-5-7-8-9-10-12 that does not contain 3.

$\endgroup$
0
$\begingroup$

A bit old post yet I guess some one might benefit from this reply. I tried to solve for the simpler graph of 12 vertices. This graph is more symmetrical and hence easier (but the method might be applicable to the 25 vertex one too).

Steps (look at earlier reply for vertex numbering)

  1. Build a path of length 10 (max path length; see previous replies too) without each of the vertices with degree 1 (3 of them). There will be three of them. For instance a path without 12 is 1-2-3-9-8-4-6-5-7-11. By symmetry it is easier to get paths without 1 and 11.
  2. Now comes the turn for removing vertices in the interior of the graph (with more than 1 as degree). Remove one such vertex e.g. 4 i.e. G-4 where G is the graph. We can get a path of length 10 (if you are counting the vertices) e.g. 1-2-3-5-6-10-9-8-7-11 without vertex 4. By symmetry other points can be removed and we can get paths of length 10.

Thus for every vertex in the graph we have shown that it is possible to get a longest path without it. Thus with a counter example we show that all longest paths need not have a common vertex.

$\endgroup$
-1
$\begingroup$

It is easy if you consider the property exhibited in the graph that says for each vertex there is a longest path now say for the labelled vertex v_1 there is a longest path P_1 and continue for all vertices in this fashion you will get collection of longest paths whose intersection will be empty.

$\endgroup$
  • $\begingroup$ I am afraid your answer is wrong. For example, in graph (b), for each vertex in {1,2,3,5,7,8,8,10,6,4}, there is path 1,2,3,5,7,8,9,10,6,4. For vertex 11, there is a path, 11,7,8,9,10,6,4,2,3,5,7. For vertex 12, there is a path, 12,10,6,4,2,3,5,7,8,9. The three paths share 9 points. $\endgroup$ – Apass.Jack Nov 24 '18 at 15:49
  • $\begingroup$ Your answer seems to be just "For each vertex, take a longest path through that vertex. The intersection of these paths is empty." But that's precisely what you're supposed to be proving! Also, what is "the property exhibited in the graph"? It's just a graph. $\endgroup$ – David Richerby Nov 24 '18 at 16:18
  • $\begingroup$ The property that these two graphs posses is that for each vertex in that graph there is a longest path which avoid this specific vertex, when we take the intersection of the collection of all such paths we get nothing see also (www.jstor.org/stable/43679284?seq=1#page_scan_tab_contents). $\endgroup$ – Yasir Bashir Nov 25 '18 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.