A New Approach Towards a Conjecture on Intersecting Three Longest Paths
Shinya Fujita$^1$
Michitaka Furuya$^2$
Reza Naserasr$^3$
Kenta Ozeki$^4$
In 1966, T. Gallai asked whether every connected graph has a vertex that appears in all longest paths. Since then this question has attracted much attention and many work has been done in this topic. One important open question in this area is to ask whether any three longest paths contains a common vertex in a connected graph. It was conjectured that the answer to this question is positive. In this paper, we propose a new approach in view of distances among longest paths in a connected graph, and give a substantial progress towards the conjecture along the idea.
f1.tex
%WinTpicVersion4.10
\unitlength 0.1in
\begin{picture}( 23.6500, 14.7200)(  6.8300,-18.2700)
% CIRCLE 2 0 0 0 Black Black
% 4 773 1092 808 1092 808 1092 808 1092
% 
\special{sh 1.000}%
\special{ia 774 1092 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 774 1092 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1053 1092 1088 1092 1088 1092 1088 1092
% 
\special{sh 1.000}%
\special{ia 1054 1092 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1054 1092 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1613 1092 1648 1092 1648 1092 1648 1092
% 
\special{sh 1.000}%
\special{ia 1614 1092 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1614 1092 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 2173 1092 2208 1092 2208 1092 2208 1092
% 
\special{sh 1.000}%
\special{ia 2174 1092 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 2174 1092 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 2733 1092 2768 1092 2768 1092 2768 1092
% 
\special{sh 1.000}%
\special{ia 2734 1092 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 2734 1092 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 3013 1092 3048 1092 3048 1092 3048 1092
% 
\special{sh 1.000}%
\special{ia 3014 1092 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 3014 1092 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black White
% 8 3013 1092 2593 1092 2313 1092 2033 1092 1753 1092 1473 1092 1193 1092 773 1092
% 
\special{pn 8}%
\special{pa 3014 1092}%
\special{pa 2594 1092}%
\special{fp}%
\special{pa 2314 1092}%
\special{pa 2034 1092}%
\special{fp}%
\special{pa 1754 1092}%
\special{pa 1474 1092}%
\special{fp}%
\special{pa 1194 1092}%
\special{pa 774 1092}%
\special{fp}%
% DOT 2 0 3 0 Black White
% 4 1893 1092 1823 1092 1963 1092 1963 1092
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 1894 1092 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1824 1092 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1964 1092 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1964 1092 6 6 0  6.28318530717959E+0000}%
% DOT 2 0 3 0 Black White
% 4 2453 1092 2383 1092 2523 1092 2523 1092
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 2454 1092 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 2384 1092 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 2524 1092 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 2524 1092 6 6 0  6.28318530717959E+0000}%
% DOT 2 0 3 0 Black White
% 4 1333 1092 1263 1092 1403 1092 1403 1092
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 1334 1092 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1264 1092 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1404 1092 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1404 1092 6 6 0  6.28318530717959E+0000}%
% STR 2 0 3 0 Black White
% 4 773 1162 773 1232 5 0 0 0
% $u$
\put(7.7300,-12.3200){\makebox(0,0){$u$}}%
% STR 2 0 3 0 Black White
% 4 3013 1162 3013 1232 5 0 0 0
% $v$
\put(30.1300,-12.3200){\makebox(0,0){$v$}}%
% STR 2 0 3 0 Black White
% 4 913 351 913 420 5 0 0 0
% $u_{1}$
\put(9.1300,-4.2000){\makebox(0,0){$u_{1}$}}%
% STR 2 0 3 0 Black White
% 4 1753 1722 1753 1792 5 0 0 0
% $v_{1}$
\put(17.5300,-17.9200){\makebox(0,0){$v_{1}$}}%
% STR 2 0 3 0 Black White
% 4 1740 1120 1740 1190 5 0 0 0
% $w_{1}$
\put(17.4000,-11.9000){\makebox(0,0){$w_{1}$}}%
% STR 2 0 3 0 Black White
% 4 2298 1127 2298 1197 5 0 0 0
% $w_{2}$
\put(22.9800,-11.9700){\makebox(0,0){$w_{2}$}}%
% STR 2 0 3 0 Black White
% 4 2873 924 2873 994 5 0 0 0
% $P$
\put(28.7300,-9.9400){\makebox(0,0){$P$}}%
% STR 2 0 3 0 Black White
% 4 1592 602 1592 672 5 0 0 0
% $P_{1}$
\put(15.9200,-6.7200){\makebox(0,0){$P_{1}$}}%
% STR 2 0 3 0 Black White
% 4 2453 756 2453 826 5 0 0 0
% $P_{2}$
\put(24.5300,-8.2600){\makebox(0,0){$P_{2}$}}%
% SPLINE 2 0 3 0 Black White
% 6 913 532 1053 952 1333 672 1613 1092 1893 1792 1893 1792
% 
\special{pn 8}%
\special{pa 914 532}%
\special{pa 920 580}%
\special{pa 926 628}%
\special{pa 934 674}%
\special{pa 940 720}%
\special{pa 948 762}%
\special{pa 956 802}%
\special{pa 964 838}%
\special{pa 974 872}%
\special{pa 986 898}%
\special{pa 996 922}%
\special{pa 1010 940}%
\special{pa 1024 950}%
\special{pa 1040 954}%
\special{pa 1056 952}%
\special{pa 1076 942}%
\special{pa 1096 924}%
\special{pa 1116 902}%
\special{pa 1138 876}%
\special{pa 1162 848}%
\special{pa 1210 788}%
\special{pa 1234 758}%
\special{pa 1258 730}%
\special{pa 1282 708}%
\special{pa 1306 688}%
\special{pa 1328 674}%
\special{pa 1352 668}%
\special{pa 1372 668}%
\special{pa 1394 676}%
\special{pa 1414 688}%
\special{pa 1434 706}%
\special{pa 1452 728}%
\special{pa 1470 754}%
\special{pa 1488 784}%
\special{pa 1506 818}%
\special{pa 1522 854}%
\special{pa 1538 892}%
\special{pa 1554 932}%
\special{pa 1570 972}%
\special{pa 1600 1054}%
\special{pa 1614 1094}%
\special{pa 1642 1170}%
\special{pa 1654 1206}%
\special{pa 1668 1242}%
\special{pa 1682 1276}%
\special{pa 1694 1308}%
\special{pa 1706 1342}%
\special{pa 1718 1374}%
\special{pa 1754 1464}%
\special{pa 1766 1492}%
\special{pa 1778 1520}%
\special{pa 1790 1548}%
\special{pa 1812 1602}%
\special{pa 1834 1654}%
\special{pa 1856 1704}%
\special{pa 1866 1730}%
\special{pa 1876 1754}%
\special{pa 1888 1778}%
\special{pa 1894 1792}%
\special{sp}%
% CIRCLE 2 0 0 0 Black Black
% 4 913 532 948 532 948 532 948 532
% 
\special{sh 1.000}%
\special{ia 914 532 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 914 532 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1893 1792 1928 1792 1928 1792 1928 1792
% 
\special{sh 1.000}%
\special{ia 1894 1792 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1894 1792 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 2 2313 812 2033 1372
% 
\special{pn 8}%
\special{pa 2314 812}%
\special{pa 2034 1372}%
\special{fp}%
% DOT 2 0 3 0 Black Black
% 4 1963 1512 1998 1442 1928 1582 1928 1582
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 1964 1512 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1998 1442 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1928 1582 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1928 1582 6 6 0  6.28318530717959E+0000}%
% DOT 2 0 3 0 Black Black
% 4 2383 672 2418 602 2348 742 2348 742
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 2384 672 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 2418 602 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 2348 742 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 2348 742 6 6 0  6.28318530717959E+0000}%
\end{picture}%

f2.tex
%WinTpicVersion4.10
\unitlength 0.1in
\begin{picture}( 36.4000, 13.2500)(  2.8300,-16.8500)
% STR 2 0 3 0 Black White
% 4 373 880 373 950 5 0 0 0
% $u$
\put(3.7300,-9.5000){\makebox(0,0){$u$}}%
% STR 2 0 3 0 Black White
% 4 3873 880 3873 950 5 0 0 0
% $v$
\put(38.7300,-9.5000){\makebox(0,0){$v$}}%
% STR 2 0 3 0 Black White
% 4 4013 642 4013 712 5 0 0 0
% $P$
\put(40.1300,-7.1200){\makebox(0,0){$P$}}%
% STR 2 0 3 0 Black White
% 4 1073 656 1073 726 5 0 0 0
% $Q_{1}$
\put(10.7300,-7.2600){\makebox(0,0){$Q_{1}$}}%
% VECTOR 2 0 3 0 Black White
% 4 968 740 793 740 1178 740 1353 740
% 
\special{pn 8}%
\special{pa 968 740}%
\special{pa 794 740}%
\special{fp}%
\special{sh 1}%
\special{pa 794 740}%
\special{pa 860 760}%
\special{pa 846 740}%
\special{pa 860 720}%
\special{pa 794 740}%
\special{fp}%
\special{pa 1178 740}%
\special{pa 1354 740}%
\special{fp}%
\special{sh 1}%
\special{pa 1354 740}%
\special{pa 1286 720}%
\special{pa 1300 740}%
\special{pa 1286 760}%
\special{pa 1354 740}%
\special{fp}%
% CIRCLE 2 0 0 0 Black Black
% 4 373 810 408 810 408 810 408 810
% 
\special{sh 1.000}%
\special{ia 374 810 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 374 810 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 793 810 828 810 828 810 828 810
% 
\special{sh 1.000}%
\special{ia 794 810 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 794 810 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1353 810 1388 810 1388 810 1388 810
% 
\special{sh 1.000}%
\special{ia 1354 810 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1354 810 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1773 810 1808 810 1808 810 1808 810
% 
\special{sh 1.000}%
\special{ia 1774 810 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1774 810 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 2333 810 2368 810 2368 810 2368 810
% 
\special{sh 1.000}%
\special{ia 2334 810 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 2334 810 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 2893 810 2928 810 2928 810 2928 810
% 
\special{sh 1.000}%
\special{ia 2894 810 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 2894 810 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 3453 810 3488 810 3488 810 3488 810
% 
\special{sh 1.000}%
\special{ia 3454 810 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 3454 810 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 3873 810 3908 810 3908 810 3908 810
% 
\special{sh 1.000}%
\special{ia 3874 810 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 3874 810 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 18 373 810 450 810 730 810 933 810 1213 810 1423 810 1703 810 1703 810 1703 810 1913 810 2193 810 2473 810 2753 810 3033 810 3313 810 3523 810 3803 810 3873 810
% 
\special{pn 8}%
\special{pa 374 810}%
\special{pa 450 810}%
\special{fp}%
\special{pa 730 810}%
\special{pa 934 810}%
\special{fp}%
\special{pa 1214 810}%
\special{pa 1424 810}%
\special{fp}%
\special{pa 1704 810}%
\special{pa 1704 810}%
\special{fp}%
\special{pa 1704 810}%
\special{pa 1914 810}%
\special{fp}%
\special{pa 2194 810}%
\special{pa 2474 810}%
\special{fp}%
\special{pa 2754 810}%
\special{pa 3034 810}%
\special{fp}%
\special{pa 3314 810}%
\special{pa 3524 810}%
\special{fp}%
\special{pa 3804 810}%
\special{pa 3874 810}%
\special{fp}%
% DOT 2 0 3 0 Black White
% 4 583 810 513 810 653 810 653 810
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 584 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 514 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 654 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 654 810 6 6 0  6.28318530717959E+0000}%
% DOT 2 0 3 0 Black White
% 4 1563 810 1493 810 1633 810 1633 810
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 1564 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1494 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1634 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1634 810 6 6 0  6.28318530717959E+0000}%
% DOT 2 0 3 0 Black White
% 4 3663 810 3593 810 3733 810 3733 810
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 3664 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 3594 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 3734 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 3734 810 6 6 0  6.28318530717959E+0000}%
% DOT 2 0 3 0 Black White
% 4 1073 810 1003 810 1143 810 1143 810
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 1074 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1004 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1144 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1144 810 6 6 0  6.28318530717959E+0000}%
% DOT 2 0 3 0 Black White
% 4 2053 810 1983 810 2123 810 2123 810
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 2054 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 1984 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 2124 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 2124 810 6 6 0  6.28318530717959E+0000}%
% DOT 2 0 3 0 Black White
% 4 2613 810 2543 810 2683 810 2683 810
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 2614 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 2544 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 2684 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 2684 810 6 6 0  6.28318530717959E+0000}%
% DOT 2 0 3 0 Black White
% 4 3173 810 3103 810 3243 810 3243 810
% 
\special{pn 4}%
\special{sh 1}%
\special{ar 3174 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 3104 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 3244 810 6 6 0  6.28318530717959E+0000}%
\special{sh 1}%
\special{ar 3244 810 6 6 0  6.28318530717959E+0000}%
% STR 2 0 3 0 Black White
% 4 2053 656 2053 726 5 0 0 0
% $Q_{2}$
\put(20.5300,-7.2600){\makebox(0,0){$Q_{2}$}}%
% VECTOR 2 0 3 0 Black White
% 4 1948 740 1773 740 2158 740 2333 740
% 
\special{pn 8}%
\special{pa 1948 740}%
\special{pa 1774 740}%
\special{fp}%
\special{sh 1}%
\special{pa 1774 740}%
\special{pa 1840 760}%
\special{pa 1826 740}%
\special{pa 1840 720}%
\special{pa 1774 740}%
\special{fp}%
\special{pa 2158 740}%
\special{pa 2334 740}%
\special{fp}%
\special{sh 1}%
\special{pa 2334 740}%
\special{pa 2266 720}%
\special{pa 2280 740}%
\special{pa 2266 760}%
\special{pa 2334 740}%
\special{fp}%
% STR 2 0 3 0 Black White
% 4 3173 656 3173 726 5 0 0 0
% $Q_{t}$
\put(31.7300,-7.2600){\makebox(0,0){$Q_{t}$}}%
% VECTOR 2 0 3 0 Black White
% 4 3068 740 2893 740 3278 740 3453 740
% 
\special{pn 8}%
\special{pa 3068 740}%
\special{pa 2894 740}%
\special{fp}%
\special{sh 1}%
\special{pa 2894 740}%
\special{pa 2960 760}%
\special{pa 2946 740}%
\special{pa 2960 720}%
\special{pa 2894 740}%
\special{fp}%
\special{pa 3278 740}%
\special{pa 3454 740}%
\special{fp}%
\special{sh 1}%
\special{pa 3454 740}%
\special{pa 3386 720}%
\special{pa 3400 740}%
\special{pa 3386 760}%
\special{pa 3454 740}%
\special{fp}%
% CIRCLE 2 0 0 0 Black Black
% 4 1073 1370 1108 1370 1108 1370 1108 1370
% 
\special{sh 1.000}%
\special{ia 1074 1370 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1074 1370 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 653 530 688 530 688 530 688 530
% 
\special{sh 1.000}%
\special{ia 654 530 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 654 530 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1493 530 1528 530 1528 530 1528 530
% 
\special{sh 1.000}%
\special{ia 1494 530 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1494 530 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1213 1650 1248 1650 1248 1650 1248 1650
% 
\special{sh 1.000}%
\special{ia 1214 1650 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1214 1650 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 933 1650 968 1650 968 1650 968 1650
% 
\special{sh 1.000}%
\special{ia 934 1650 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 934 1650 36 36  0.0000000 6.2831853}%
% STR 2 0 3 0 Black Black
% 4 1025 877 1025 947 5 0 0 0
% $w^{(1)}_{1}$
\put(10.2500,-9.4700){\makebox(0,0){$w^{(1)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 1422 880 1422 950 5 0 0 0
% $w^{(2)}_{1}$
\put(14.2200,-9.5000){\makebox(0,0){$w^{(2)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 1773 880 1773 950 5 0 0 0
% $w^{(2)}_{2}$
\put(17.7300,-9.5000){\makebox(0,0){$w^{(2)}_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 2333 880 2333 950 5 0 0 0
% $w^{(1)}_{2}$
\put(23.3300,-9.5000){\makebox(0,0){$w^{(1)}_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 1493 356 1493 425 5 0 0 0
% $u_{2}$
\put(14.9300,-4.2500){\makebox(0,0){$u_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 653 356 653 425 5 0 0 0
% $u_{1}$
\put(6.5300,-4.2500){\makebox(0,0){$u_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 793 1580 793 1650 5 0 0 0
% $v_{2}$
\put(7.9300,-16.5000){\makebox(0,0){$v_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 1353 1580 1353 1650 5 0 0 0
% $v_{1}$
\put(13.5300,-16.5000){\makebox(0,0){$v_{1}$}}%
% STR 2 0 3 0 Black White
% 4 1199 1297 1199 1367 5 0 0 0
% $x$
\put(11.9900,-13.6700){\makebox(0,0){$x$}}%
% LINE 2 0 3 0 Black White
% 4 653 534 1213 1654 933 1654 1493 534
% 
\special{pn 8}%
\special{pa 654 534}%
\special{pa 1214 1654}%
\special{fp}%
\special{pa 934 1654}%
\special{pa 1494 534}%
\special{fp}%
% STR 2 0 3 0 Black White
% 4 1514 597 1514 667 5 0 0 0
% $P_{2}$
\put(15.1400,-6.6700){\makebox(0,0){$P_{2}$}}%
% STR 2 0 3 0 Black White
% 4 632 597 632 667 5 0 0 0
% $P_{1}$
\put(6.3200,-6.6700){\makebox(0,0){$P_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 856 1024 856 1094 5 0 0 0
% $R$
\put(8.5600,-10.9400){\makebox(0,0){$R$}}%
% VECTOR 2 0 3 0 Black Black
% 2 891 1150 989 1353
% 
\special{pn 8}%
\special{pa 892 1150}%
\special{pa 990 1354}%
\special{fp}%
\special{sh 1}%
\special{pa 990 1354}%
\special{pa 978 1284}%
\special{pa 966 1306}%
\special{pa 942 1302}%
\special{pa 990 1354}%
\special{fp}%
% VECTOR 2 0 3 0 Black Black
% 2 835 1045 737 842
% 
\special{pn 8}%
\special{pa 836 1046}%
\special{pa 738 842}%
\special{fp}%
\special{sh 1}%
\special{pa 738 842}%
\special{pa 748 912}%
\special{pa 760 890}%
\special{pa 784 894}%
\special{pa 738 842}%
\special{fp}%
\end{picture}%

f3.tex
%WinTpicVersion4.10
\unitlength 0.1in
\begin{picture}( 58.8000, 13.2200)(  2.8300,-16.9200)
% STR 2 0 3 0 Black White
% 4 373 890 373 960 5 0 0 0
% $u$
\put(3.7300,-9.6000){\makebox(0,0){$u$}}%
% STR 2 0 3 0 Black Black
% 4 704 887 704 957 5 0 0 0
% $w^{(1)}_{1}$
\put(7.0400,-9.5700){\makebox(0,0){$w^{(1)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 1422 890 1422 960 5 0 0 0
% $w^{(2)}_{1}$
\put(14.2200,-9.6000){\makebox(0,0){$w^{(2)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 1493 366 1493 435 5 0 0 0
% $u_{2}$
\put(14.9300,-4.3500){\makebox(0,0){$u_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 653 366 653 435 5 0 0 0
% $u_{1}$
\put(6.5300,-4.3500){\makebox(0,0){$u_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 793 1590 793 1660 5 0 0 0
% $v_{2}$
\put(7.9300,-16.6000){\makebox(0,0){$v_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 1353 1590 1353 1660 5 0 0 0
% $v_{1}$
\put(13.5300,-16.6000){\makebox(0,0){$v_{1}$}}%
% STR 2 0 3 0 Black White
% 4 1192 1310 1192 1380 5 0 0 0
% $x$
\put(11.9200,-13.8000){\makebox(0,0){$x$}}%
% STR 2 0 3 0 Black White
% 4 1544 607 1544 677 5 0 0 0
% $P_{2}$
\put(15.4400,-6.7700){\makebox(0,0){$P_{2}$}}%
% STR 2 0 3 0 Black White
% 4 610 600 610 670 5 0 0 0
% $P_{1}$
\put(6.1000,-6.7000){\makebox(0,0){$P_{1}$}}%
% CIRCLE 2 0 0 0 Black Black
% 4 373 817 408 817 408 817 408 817
% 
\special{sh 1.000}%
\special{ia 374 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 374 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 793 817 828 817 828 817 828 817
% 
\special{sh 1.000}%
\special{ia 794 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 794 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1353 817 1388 817 1388 817 1388 817
% 
\special{sh 1.000}%
\special{ia 1354 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1354 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1913 817 1948 817 1948 817 1948 817
% 
\special{sh 1.000}%
\special{ia 1914 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1914 818 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 4 653 537 1213 1657 1493 537 933 1657
% 
\special{pn 8}%
\special{pa 654 538}%
\special{pa 1214 1658}%
\special{fp}%
\special{pa 1494 538}%
\special{pa 934 1658}%
\special{fp}%
% CIRCLE 2 0 0 0 Black Black
% 4 1493 537 1528 537 1528 537 1528 537
% 
\special{sh 1.000}%
\special{ia 1494 538 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1494 538 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 653 537 688 537 688 537 688 537
% 
\special{sh 1.000}%
\special{ia 654 538 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 654 538 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1073 1377 1108 1377 1108 1377 1108 1377
% 
\special{sh 1.000}%
\special{ia 1074 1378 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1074 1378 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 933 1657 968 1657 968 1657 968 1657
% 
\special{sh 1.000}%
\special{ia 934 1658 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 934 1658 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1213 1657 1248 1657 1248 1657 1248 1657
% 
\special{sh 1.000}%
\special{ia 1214 1658 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1214 1658 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 2 373 817 1913 817
% 
\special{pn 8}%
\special{pa 374 818}%
\special{pa 1914 818}%
\special{fp}%
% LINE 2 0 3 0 Black Black
% 4 884 1608 1248 880 898 880 1248 880
% 
\special{pn 8}%
\special{pa 884 1608}%
\special{pa 1248 880}%
\special{fp}%
\special{pa 898 880}%
\special{pa 1248 880}%
\special{fp}%
% VECTOR 2 0 3 0 Black Black
% 2 898 880 1038 1160
% 
\special{pn 8}%
\special{pa 898 880}%
\special{pa 1038 1160}%
\special{fp}%
\special{sh 1}%
\special{pa 1038 1160}%
\special{pa 1026 1092}%
\special{pa 1014 1112}%
\special{pa 990 1110}%
\special{pa 1038 1160}%
\special{fp}%
% STR 2 0 3 0 Black White
% 4 1913 883 1913 953 5 0 0 0
% $v$
\put(19.1300,-9.5300){\makebox(0,0){$v$}}%
% STR 2 0 3 0 Black White
% 4 2053 645 2053 715 5 0 0 0
% $P$
\put(20.5300,-7.1500){\makebox(0,0){$P$}}%
% STR 2 0 3 0 Black White
% 4 4573 890 4573 960 5 0 0 0
% $u$
\put(45.7300,-9.6000){\makebox(0,0){$u$}}%
% STR 2 0 3 0 Black Black
% 4 4904 887 4904 957 5 0 0 0
% $w^{(1)}_{1}$
\put(49.0400,-9.5700){\makebox(0,0){$w^{(1)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 5622 890 5622 960 5 0 0 0
% $w^{(2)}_{1}$
\put(56.2200,-9.6000){\makebox(0,0){$w^{(2)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 5693 366 5693 435 5 0 0 0
% $u_{2}$
\put(56.9300,-4.3500){\makebox(0,0){$u_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 4853 366 4853 435 5 0 0 0
% $u_{1}$
\put(48.5300,-4.3500){\makebox(0,0){$u_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 4993 1590 4993 1660 5 0 0 0
% $v_{2}$
\put(49.9300,-16.6000){\makebox(0,0){$v_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 5553 1590 5553 1660 5 0 0 0
% $v_{1}$
\put(55.5300,-16.6000){\makebox(0,0){$v_{1}$}}%
% STR 2 0 3 0 Black White
% 4 5392 1310 5392 1380 5 0 0 0
% $x$
\put(53.9200,-13.8000){\makebox(0,0){$x$}}%
% STR 2 0 3 0 Black White
% 4 5744 607 5744 677 5 0 0 0
% $P_{2}$
\put(57.4400,-6.7700){\makebox(0,0){$P_{2}$}}%
% STR 2 0 3 0 Black White
% 4 4812 607 4812 677 5 0 0 0
% $P_{1}$
\put(48.1200,-6.7700){\makebox(0,0){$P_{1}$}}%
% STR 2 0 3 0 Black White
% 4 6113 883 6113 953 5 0 0 0
% $v$
\put(61.1300,-9.5300){\makebox(0,0){$v$}}%
% STR 2 0 3 0 Black White
% 4 6253 645 6253 715 5 0 0 0
% $P$
\put(62.5300,-7.1500){\makebox(0,0){$P$}}%
% CIRCLE 2 0 0 0 Black Black
% 4 2473 817 2508 817 2508 817 2508 817
% 
\special{sh 1.000}%
\special{ia 2474 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 2474 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 2893 817 2928 817 2928 817 2928 817
% 
\special{sh 1.000}%
\special{ia 2894 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 2894 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 3453 817 3488 817 3488 817 3488 817
% 
\special{sh 1.000}%
\special{ia 3454 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 3454 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 4013 817 4048 817 4048 817 4048 817
% 
\special{sh 1.000}%
\special{ia 4014 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 4014 818 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 4 2753 537 3313 1657 3593 537 3033 1657
% 
\special{pn 8}%
\special{pa 2754 538}%
\special{pa 3314 1658}%
\special{fp}%
\special{pa 3594 538}%
\special{pa 3034 1658}%
\special{fp}%
% CIRCLE 2 0 0 0 Black Black
% 4 3593 537 3628 537 3628 537 3628 537
% 
\special{sh 1.000}%
\special{ia 3594 538 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 3594 538 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 2753 537 2788 537 2788 537 2788 537
% 
\special{sh 1.000}%
\special{ia 2754 538 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 2754 538 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 3173 1377 3208 1377 3208 1377 3208 1377
% 
\special{sh 1.000}%
\special{ia 3174 1378 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 3174 1378 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 3033 1657 3068 1657 3068 1657 3068 1657
% 
\special{sh 1.000}%
\special{ia 3034 1658 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 3034 1658 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 3313 1657 3348 1657 3348 1657 3348 1657
% 
\special{sh 1.000}%
\special{ia 3314 1658 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 3314 1658 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 2 2473 817 4013 817
% 
\special{pn 8}%
\special{pa 2474 818}%
\special{pa 4014 818}%
\special{fp}%
% CIRCLE 2 0 0 0 Black Black
% 4 4573 817 4608 817 4608 817 4608 817
% 
\special{sh 1.000}%
\special{ia 4574 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 4574 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 4993 817 5028 817 5028 817 5028 817
% 
\special{sh 1.000}%
\special{ia 4994 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 4994 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 5553 817 5588 817 5588 817 5588 817
% 
\special{sh 1.000}%
\special{ia 5554 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 5554 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 6113 817 6148 817 6148 817 6148 817
% 
\special{sh 1.000}%
\special{ia 6114 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 6114 818 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 4 4853 537 5413 1657 5693 537 5133 1657
% 
\special{pn 8}%
\special{pa 4854 538}%
\special{pa 5414 1658}%
\special{fp}%
\special{pa 5694 538}%
\special{pa 5134 1658}%
\special{fp}%
% CIRCLE 2 0 0 0 Black Black
% 4 5693 537 5728 537 5728 537 5728 537
% 
\special{sh 1.000}%
\special{ia 5694 538 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 5694 538 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 4853 537 4888 537 4888 537 4888 537
% 
\special{sh 1.000}%
\special{ia 4854 538 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 4854 538 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 5273 1377 5308 1377 5308 1377 5308 1377
% 
\special{sh 1.000}%
\special{ia 5274 1378 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 5274 1378 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 5133 1657 5168 1657 5168 1657 5168 1657
% 
\special{sh 1.000}%
\special{ia 5134 1658 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 5134 1658 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 5413 1657 5448 1657 5448 1657 5448 1657
% 
\special{sh 1.000}%
\special{ia 5414 1658 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 5414 1658 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 2 4573 817 6113 817
% 
\special{pn 8}%
\special{pa 4574 818}%
\special{pa 6114 818}%
\special{fp}%
% LINE 2 0 3 0 Black Black
% 6 3530 516 3348 880 3348 880 2998 880 2998 880 3173 1230
% 
\special{pn 8}%
\special{pa 3530 516}%
\special{pa 3348 880}%
\special{fp}%
\special{pa 3348 880}%
\special{pa 2998 880}%
\special{fp}%
\special{pa 2998 880}%
\special{pa 3174 1230}%
\special{fp}%
% VECTOR 2 0 3 0 Black Black
% 2 3173 1230 2984 1608
% 
\special{pn 8}%
\special{pa 3174 1230}%
\special{pa 2984 1608}%
\special{fp}%
\special{sh 1}%
\special{pa 2984 1608}%
\special{pa 3032 1558}%
\special{pa 3008 1560}%
\special{pa 2996 1540}%
\special{pa 2984 1608}%
\special{fp}%
% STR 2 0 3 0 Black White
% 4 2473 890 2473 960 5 0 0 0
% $u$
\put(24.7300,-9.6000){\makebox(0,0){$u$}}%
% STR 2 0 3 0 Black Black
% 4 2804 887 2804 957 5 0 0 0
% $w^{(1)}_{1}$
\put(28.0400,-9.5700){\makebox(0,0){$w^{(1)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 3522 890 3522 960 5 0 0 0
% $w^{(2)}_{1}$
\put(35.2200,-9.6000){\makebox(0,0){$w^{(2)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 3593 366 3593 435 5 0 0 0
% $u_{2}$
\put(35.9300,-4.3500){\makebox(0,0){$u_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 2753 366 2753 435 5 0 0 0
% $u_{1}$
\put(27.5300,-4.3500){\makebox(0,0){$u_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 2893 1590 2893 1660 5 0 0 0
% $v_{2}$
\put(28.9300,-16.6000){\makebox(0,0){$v_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 3453 1590 3453 1660 5 0 0 0
% $v_{1}$
\put(34.5300,-16.6000){\makebox(0,0){$v_{1}$}}%
% STR 2 0 3 0 Black White
% 4 3292 1310 3292 1380 5 0 0 0
% $x$
\put(32.9200,-13.8000){\makebox(0,0){$x$}}%
% STR 2 0 3 0 Black White
% 4 3644 607 3644 677 5 0 0 0
% $P_{2}$
\put(36.4400,-6.7700){\makebox(0,0){$P_{2}$}}%
% STR 2 0 3 0 Black White
% 4 2712 607 2712 677 5 0 0 0
% $P_{1}$
\put(27.1200,-6.7700){\makebox(0,0){$P_{1}$}}%
% STR 2 0 3 0 Black White
% 4 4013 883 4013 953 5 0 0 0
% $v$
\put(40.1300,-9.5300){\makebox(0,0){$v$}}%
% STR 2 0 3 0 Black White
% 4 4153 645 4153 715 5 0 0 0
% $P$
\put(41.5300,-7.1500){\makebox(0,0){$P$}}%
% LINE 2 0 3 0 Black Black
% 4 5630 516 5273 1230 5273 1230 5098 880
% 
\special{pn 8}%
\special{pa 5630 516}%
\special{pa 5274 1230}%
\special{fp}%
\special{pa 5274 1230}%
\special{pa 5098 880}%
\special{fp}%
% VECTOR 2 0 3 0 Black Black
% 2 5098 880 5378 880
% 
\special{pn 8}%
\special{pa 5098 880}%
\special{pa 5378 880}%
\special{fp}%
\special{sh 1}%
\special{pa 5378 880}%
\special{pa 5312 860}%
\special{pa 5326 880}%
\special{pa 5312 900}%
\special{pa 5378 880}%
\special{fp}%
% STR 2 0 3 0 Black White
% 4 875 1342 875 1412 5 0 0 0
% $S_{1}$
\put(8.7500,-14.1200){\makebox(0,0){$S_{1}$}}%
% STR 2 0 3 0 Black White
% 4 2975 1342 2975 1412 5 0 0 0
% $S_{2}$
\put(29.7500,-14.1200){\makebox(0,0){$S_{2}$}}%
% STR 2 0 3 0 Black White
% 4 5490 500 5490 570 5 0 0 0
% $S_{3}$
\put(54.9000,-5.7000){\makebox(0,0){$S_{3}$}}%
\end{picture}%

f4.tex
%WinTpicVersion4.10
\unitlength 0.1in
\begin{picture}( 25.2000, 13.2200)(  4.8300,-16.9200)
% STR 2 0 3 0 Black White
% 4 573 890 573 960 5 0 0 0
% $u$
\put(5.7300,-9.6000){\makebox(0,0){$u$}}%
% STR 2 0 3 0 Black Black
% 4 924 897 924 967 5 0 0 0
% $w^{(1)}_{1}$
\put(9.2400,-9.6700){\makebox(0,0){$w^{(1)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 1632 890 1632 960 5 0 0 0
% $w^{(2)}_{1}$
\put(16.3200,-9.6000){\makebox(0,0){$w^{(2)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 1693 366 1693 435 5 0 0 0
% $u_{2}$
\put(16.9300,-4.3500){\makebox(0,0){$u_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 853 366 853 435 5 0 0 0
% $u_{1}$
\put(8.5300,-4.3500){\makebox(0,0){$u_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 993 1590 993 1660 5 0 0 0
% $v_{2}$
\put(9.9300,-16.6000){\makebox(0,0){$v_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 1553 1590 1553 1660 5 0 0 0
% $v_{1}$
\put(15.5300,-16.6000){\makebox(0,0){$v_{1}$}}%
% STR 2 0 3 0 Black White
% 4 1392 1310 1392 1380 5 0 0 0
% $x$
\put(13.9200,-13.8000){\makebox(0,0){$x$}}%
% STR 2 0 3 0 Black White
% 4 1714 607 1714 677 5 0 0 0
% $P_{2}$
\put(17.1400,-6.7700){\makebox(0,0){$P_{2}$}}%
% STR 2 0 3 0 Black White
% 4 832 607 832 677 5 0 0 0
% $P_{1}$
\put(8.3200,-6.7700){\makebox(0,0){$P_{1}$}}%
% STR 2 0 3 0 Black White
% 4 2953 883 2953 953 5 0 0 0
% $v$
\put(29.5300,-9.5300){\makebox(0,0){$v$}}%
% STR 2 0 3 0 Black White
% 4 3093 642 3093 712 5 0 0 0
% $P$
\put(30.9300,-7.1200){\makebox(0,0){$P$}}%
% CIRCLE 2 0 0 0 Black Black
% 4 573 817 608 817 608 817 608 817
% 
\special{sh 1.000}%
\special{ia 574 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 574 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 993 817 1028 817 1028 817 1028 817
% 
\special{sh 1.000}%
\special{ia 994 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 994 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1553 817 1588 817 1588 817 1588 817
% 
\special{sh 1.000}%
\special{ia 1554 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1554 818 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 4 853 537 1413 1657 1693 537 1133 1657
% 
\special{pn 8}%
\special{pa 854 538}%
\special{pa 1414 1658}%
\special{fp}%
\special{pa 1694 538}%
\special{pa 1134 1658}%
\special{fp}%
% CIRCLE 2 0 0 0 Black Black
% 4 1693 537 1728 537 1728 537 1728 537
% 
\special{sh 1.000}%
\special{ia 1694 538 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1694 538 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 853 537 888 537 888 537 888 537
% 
\special{sh 1.000}%
\special{ia 854 538 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 854 538 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1273 1377 1308 1377 1308 1377 1308 1377
% 
\special{sh 1.000}%
\special{ia 1274 1378 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1274 1378 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1133 1657 1168 1657 1168 1657 1168 1657
% 
\special{sh 1.000}%
\special{ia 1134 1658 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1134 1658 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1413 1657 1448 1657 1448 1657 1448 1657
% 
\special{sh 1.000}%
\special{ia 1414 1658 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1414 1658 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1973 817 2008 817 2008 817 2008 817
% 
\special{sh 1.000}%
\special{ia 1974 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1974 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 2533 817 2568 817 2568 817 2568 817
% 
\special{sh 1.000}%
\special{ia 2534 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 2534 818 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 2953 817 2988 817 2988 817 2988 817
% 
\special{sh 1.000}%
\special{ia 2954 818 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 2954 818 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 2 2953 817 573 817
% 
\special{pn 8}%
\special{pa 2954 818}%
\special{pa 574 818}%
\special{fp}%
% LINE 2 0 3 0 Black Black
% 2 1448 880 573 880
% 
\special{pn 8}%
\special{pa 1448 880}%
\special{pa 574 880}%
\special{fp}%
% VECTOR 2 0 3 0 Black Black
% 2 1448 880 1063 1650
% 
\special{pn 8}%
\special{pa 1448 880}%
\special{pa 1064 1650}%
\special{fp}%
\special{sh 1}%
\special{pa 1064 1650}%
\special{pa 1112 1600}%
\special{pa 1088 1602}%
\special{pa 1076 1582}%
\special{pa 1064 1650}%
\special{fp}%
% STR 2 0 3 0 Black White
% 4 1098 1307 1098 1377 5 0 0 0
% $T$
\put(10.9800,-13.7700){\makebox(0,0){$T$}}%
% STR 2 0 3 0 Black Black
% 4 1973 887 1973 957 5 0 0 0
% $w^{(2)}_{2}$
\put(19.7300,-9.5700){\makebox(0,0){$w^{(2)}_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 2533 887 2533 957 5 0 0 0
% $w^{(1)}_{2}$
\put(25.3300,-9.5700){\makebox(0,0){$w^{(1)}_{2}$}}%
\end{picture}%

f5.tex
%WinTpicVersion4.10
\unitlength 0.1in
\begin{picture}( 54.6000, 13.2200)(  4.8300,-18.9200)
% STR 2 0 3 0 Black White
% 4 3513 1090 3513 1160 5 0 0 0
% $u$
\put(35.1300,-11.6000){\makebox(0,0){$u$}}%
% STR 2 0 3 0 Black Black
% 4 3854 1087 3854 1157 5 0 0 0
% $w^{(1)}_{1}$
\put(38.5400,-11.5700){\makebox(0,0){$w^{(1)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 4562 1100 4562 1170 5 0 0 0
% $w^{(2)}_{1}$
\put(45.6200,-11.7000){\makebox(0,0){$w^{(2)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 4633 566 4633 635 5 0 0 0
% $u_{2}$
\put(46.3300,-6.3500){\makebox(0,0){$u_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 3793 566 3793 635 5 0 0 0
% $u_{1}$
\put(37.9300,-6.3500){\makebox(0,0){$u_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 3933 1790 3933 1860 5 0 0 0
% $v_{2}$
\put(39.3300,-18.6000){\makebox(0,0){$v_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 4523 1790 4523 1860 5 0 0 0
% $v_{1}$
\put(45.2300,-18.6000){\makebox(0,0){$v_{1}$}}%
% STR 2 0 3 0 Black White
% 4 4108 1507 4108 1577 5 0 0 0
% $x$
\put(41.0800,-15.7700){\makebox(0,0){$x$}}%
% STR 2 0 3 0 Black White
% 4 4654 807 4654 877 5 0 0 0
% $P_{2}$
\put(46.5400,-8.7700){\makebox(0,0){$P_{2}$}}%
% STR 2 0 3 0 Black White
% 4 3772 807 3772 877 5 0 0 0
% $P_{1}$
\put(37.7200,-8.7700){\makebox(0,0){$P_{1}$}}%
% STR 2 0 3 0 Black White
% 4 5893 1083 5893 1153 5 0 0 0
% $v$
\put(58.9300,-11.5300){\makebox(0,0){$v$}}%
% STR 2 0 3 0 Black White
% 4 6033 845 6033 915 5 0 0 0
% $P$
\put(60.3300,-9.1500){\makebox(0,0){$P$}}%
% CIRCLE 2 0 0 0 Black Black
% 4 3513 1017 3548 1017 3548 1017 3548 1017
% 
\special{sh 1.000}%
\special{ia 3514 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 3514 1018 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 3933 1017 3968 1017 3968 1017 3968 1017
% 
\special{sh 1.000}%
\special{ia 3934 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 3934 1018 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 4493 1017 4528 1017 4528 1017 4528 1017
% 
\special{sh 1.000}%
\special{ia 4494 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 4494 1018 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 4 3793 737 4353 1857 4633 737 4073 1857
% 
\special{pn 8}%
\special{pa 3794 738}%
\special{pa 4354 1858}%
\special{fp}%
\special{pa 4634 738}%
\special{pa 4074 1858}%
\special{fp}%
% CIRCLE 2 0 0 0 Black Black
% 4 4633 737 4668 737 4668 737 4668 737
% 
\special{sh 1.000}%
\special{ia 4634 738 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 4634 738 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 3793 737 3828 737 3828 737 3828 737
% 
\special{sh 1.000}%
\special{ia 3794 738 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 3794 738 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 4213 1577 4248 1577 4248 1577 4248 1577
% 
\special{sh 1.000}%
\special{ia 4214 1578 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 4214 1578 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 4073 1857 4108 1857 4108 1857 4108 1857
% 
\special{sh 1.000}%
\special{ia 4074 1858 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 4074 1858 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 4353 1857 4388 1857 4388 1857 4388 1857
% 
\special{sh 1.000}%
\special{ia 4354 1858 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 4354 1858 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 4913 1017 4948 1017 4948 1017 4948 1017
% 
\special{sh 1.000}%
\special{ia 4914 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 4914 1018 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 5473 1017 5508 1017 5508 1017 5508 1017
% 
\special{sh 1.000}%
\special{ia 5474 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 5474 1018 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 5893 1017 5928 1017 5928 1017 5928 1017
% 
\special{sh 1.000}%
\special{ia 5894 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 5894 1018 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 2 5893 1017 3513 1017
% 
\special{pn 8}%
\special{pa 5894 1018}%
\special{pa 3514 1018}%
\special{fp}%
% LINE 2 0 3 0 Black Black
% 2 4038 1080 5382 1080
% 
\special{pn 8}%
\special{pa 4038 1080}%
\special{pa 5382 1080}%
\special{fp}%
% VECTOR 2 0 3 0 Black Black
% 2 4038 1080 4423 1850
% 
\special{pn 8}%
\special{pa 4038 1080}%
\special{pa 4424 1850}%
\special{fp}%
\special{sh 1}%
\special{pa 4424 1850}%
\special{pa 4412 1782}%
\special{pa 4400 1802}%
\special{pa 4376 1800}%
\special{pa 4424 1850}%
\special{fp}%
% STR 2 0 3 0 Black Black
% 4 4920 1100 4920 1170 5 0 0 0
% $w^{(2)}_{2}$
\put(49.2000,-11.7000){\makebox(0,0){$w^{(2)}_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 5480 1097 5480 1167 5 0 0 0
% $w^{(1)}_{2}$
\put(54.8000,-11.6700){\makebox(0,0){$w^{(1)}_{2}$}}%
% STR 2 0 3 0 Black White
% 4 4410 1549 4410 1619 5 0 0 0
% $T_{2}$
\put(44.1000,-16.1900){\makebox(0,0){$T_{2}$}}%
% STR 2 0 3 0 Black White
% 4 573 1090 573 1160 5 0 0 0
% $u$
\put(5.7300,-11.6000){\makebox(0,0){$u$}}%
% STR 2 0 3 0 Black Black
% 4 914 1087 914 1157 5 0 0 0
% $w^{(1)}_{1}$
\put(9.1400,-11.5700){\makebox(0,0){$w^{(1)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 1622 1100 1622 1170 5 0 0 0
% $w^{(2)}_{1}$
\put(16.2200,-11.7000){\makebox(0,0){$w^{(2)}_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 1693 566 1693 635 5 0 0 0
% $u_{2}$
\put(16.9300,-6.3500){\makebox(0,0){$u_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 853 566 853 635 5 0 0 0
% $u_{1}$
\put(8.5300,-6.3500){\makebox(0,0){$u_{1}$}}%
% STR 2 0 3 0 Black Black
% 4 993 1790 993 1860 5 0 0 0
% $v_{2}$
\put(9.9300,-18.6000){\makebox(0,0){$v_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 1553 1790 1553 1860 5 0 0 0
% $v_{1}$
\put(15.5300,-18.6000){\makebox(0,0){$v_{1}$}}%
% STR 2 0 3 0 Black White
% 4 1168 1507 1168 1577 5 0 0 0
% $x$
\put(11.6800,-15.7700){\makebox(0,0){$x$}}%
% STR 2 0 3 0 Black White
% 4 1714 807 1714 877 5 0 0 0
% $P_{2}$
\put(17.1400,-8.7700){\makebox(0,0){$P_{2}$}}%
% STR 2 0 3 0 Black White
% 4 832 807 832 877 5 0 0 0
% $P_{1}$
\put(8.3200,-8.7700){\makebox(0,0){$P_{1}$}}%
% STR 2 0 3 0 Black White
% 4 2953 1083 2953 1153 5 0 0 0
% $v$
\put(29.5300,-11.5300){\makebox(0,0){$v$}}%
% STR 2 0 3 0 Black White
% 4 3093 845 3093 915 5 0 0 0
% $P$
\put(30.9300,-9.1500){\makebox(0,0){$P$}}%
% CIRCLE 2 0 0 0 Black Black
% 4 573 1017 608 1017 608 1017 608 1017
% 
\special{sh 1.000}%
\special{ia 574 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 574 1018 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 993 1017 1028 1017 1028 1017 1028 1017
% 
\special{sh 1.000}%
\special{ia 994 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 994 1018 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1553 1017 1588 1017 1588 1017 1588 1017
% 
\special{sh 1.000}%
\special{ia 1554 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1554 1018 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 4 853 737 1413 1857 1693 737 1133 1857
% 
\special{pn 8}%
\special{pa 854 738}%
\special{pa 1414 1858}%
\special{fp}%
\special{pa 1694 738}%
\special{pa 1134 1858}%
\special{fp}%
% CIRCLE 2 0 0 0 Black Black
% 4 1693 737 1728 737 1728 737 1728 737
% 
\special{sh 1.000}%
\special{ia 1694 738 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1694 738 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 853 737 888 737 888 737 888 737
% 
\special{sh 1.000}%
\special{ia 854 738 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 854 738 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1273 1577 1308 1577 1308 1577 1308 1577
% 
\special{sh 1.000}%
\special{ia 1274 1578 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1274 1578 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1133 1857 1168 1857 1168 1857 1168 1857
% 
\special{sh 1.000}%
\special{ia 1134 1858 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1134 1858 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1413 1857 1448 1857 1448 1857 1448 1857
% 
\special{sh 1.000}%
\special{ia 1414 1858 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1414 1858 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 1973 1017 2008 1017 2008 1017 2008 1017
% 
\special{sh 1.000}%
\special{ia 1974 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 1974 1018 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 2533 1017 2568 1017 2568 1017 2568 1017
% 
\special{sh 1.000}%
\special{ia 2534 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 2534 1018 36 36  0.0000000 6.2831853}%
% CIRCLE 2 0 0 0 Black Black
% 4 2953 1017 2988 1017 2988 1017 2988 1017
% 
\special{sh 1.000}%
\special{ia 2954 1018 36 36  0.0000000 6.2831853}%
\special{pn 8}%
\special{ar 2954 1018 36 36  0.0000000 6.2831853}%
% LINE 2 0 3 0 Black Black
% 2 2953 1017 573 1017
% 
\special{pn 8}%
\special{pa 2954 1018}%
\special{pa 574 1018}%
\special{fp}%
% LINE 2 0 3 0 Black Black
% 2 1098 1080 2442 1080
% 
\special{pn 8}%
\special{pa 1098 1080}%
\special{pa 2442 1080}%
\special{fp}%
% STR 2 0 3 0 Black Black
% 4 1980 1100 1980 1170 5 0 0 0
% $w^{(2)}_{2}$
\put(19.8000,-11.7000){\makebox(0,0){$w^{(2)}_{2}$}}%
% STR 2 0 3 0 Black Black
% 4 2540 1097 2540 1167 5 0 0 0
% $w^{(1)}_{2}$
\put(25.4000,-11.6700){\makebox(0,0){$w^{(1)}_{2}$}}%
% VECTOR 2 0 3 0 Black Black
% 2 1098 1080 916 716
% 
\special{pn 8}%
\special{pa 1098 1080}%
\special{pa 916 716}%
\special{fp}%
\special{sh 1}%
\special{pa 916 716}%
\special{pa 928 786}%
\special{pa 940 764}%
\special{pa 964 768}%
\special{pa 916 716}%
\special{fp}%
% STR 2 0 3 0 Black Black
% 4 1056 800 1056 870 5 0 0 0
% $T_{1}$
\put(10.5600,-8.7000){\makebox(0,0){$T_{1}$}}%
\end{picture}%

three_path_final.tex
\documentclass[12pt,a4paper]{article}

%%%%%%%%%%% MACRO %%%%%%%%%%
\usepackage{theorem,enumerate}
\usepackage{amsmath,latexsym,amssymb,amsfonts}
\usepackage{eucal}
\usepackage{eufrak}
%\usepackage{mathrsfs}

%%%%%Counter%%%%%
\newcounter{Scounter}
\setcounter{Scounter}{1}
\def\sco{\arabic{Scounter}}
\def\ssco{\stepcounter{Scounter}}
\def\sets{\setcounter{Scounter}{1}}

%%%%%%%%%%% Theorem %%%%%%%%%%
\theorembodyfont{\normalfont\slshape}
\newtheorem{thm}{Theorem}
\newtheorem{refthm}[thm]{Theorem}
\newtheorem{Thm}{Theorem}
\renewcommand{\theThm}{\Alph{Thm}}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{obs}[thm]{Observation}
\newtheorem{Q}[thm]{Question} 
%\newtheorem{Q}{Question} 
\renewcommand{\theQ}{}
\newtheorem{claim}{Claim}
\newtheorem{subclaim}{Subclaim}[claim]
%\renewcommand{\thesubclaim}{}
\newtheorem{fact}[claim]{Fact} 
\newtheorem{con}[thm]{Conjecture}
\newtheorem{pro}{Problem}

\newcommand{\proof}{\medbreak\noindent\textit{Proof.}\quad}
\newcommand{\Proof}{\medbreak\noindent\textbf{Proof.}\quad}
\newcommand{\PROOF}[1]{\medbreak\noindent\textbf{Proof #1.}\ }
\newcommand{\proofA}{\medbreak\noindent\textit{Proof of Theorem A.}\quad}


\newcommand{\case}[1]{\noin{\it Case #1}}
\newcommand{\Case}[1]{\noin{\bf Case #1}}
\newcommand{\sscase}[2]{\noin{\bf (#1) }#2}
\newcommand{\qed}{{$\quad\square$\vs{3.6}}}
\newcommand{\Qed}{{$\;\square$\vs{3.6}}}
\newcommand{\qqed}{{$\quad\square \square$\vs{3.6}}}

\newcommand{\diff}{\text{\upshape diff}}
\newcommand{\bss}{\setminus}

\newcommand{\uppercut}[1]{\left\lceil #1 \right\rceil}
\newcommand{\vs}[1]{\vspace*{#1 mm}}
\newcommand{\hs}[1]{\hspace*{#1 mm}}
\newcommand{\noin}{\noindent}
\newcommand{\bs}{\setminus}
\newcommand{\kuu}[1]{{#1}'}
\newcommand{\hasi}[1]{\tilde{#1}}
\newcommand{\hasis}[1]{\tilde{#1}}
\newcommand{\dg}[2]{d_{#1}(#2)}
\newcommand{\bun}[2]{\frac{#1}{#2}}
\newcommand{\IRO}[2]{#1\ora{C}#2^-}
\newcommand{\OIR}[2]{#1^+\ora{C}#2}
\newcommand{\OIRO}[2]{#1^+\ora{C}#2^-}
\newcommand{\PR}[2]{P[#1,#2]}
\newcommand{\IR}[2]{#1\ora{C}#2}
\newcommand{\IL}[2]{#1\ola{C}#2}
\newcommand{\ep}{\varepsilon}

\numberwithin{equation}{section}

\newcommand{\el}{l}

\def\L{{ \mathcal{L}}}
\def\T{{ \mathcal{T}}}
\def\P{{ \mathcal{P}}}
\def\F{{ \mathcal{F}}}
\def\H{{ \mathscr{H}}}
\def\C{{ \mathscr{C}}}
\def\I{{ \mathcal{I}}}
\def\Q{{ \mathcal{Q}}}
\def\T{{ \mathcal{T}}}

%%%%%orientation%%%%%%
\newcommand{\ora}{\overrightarrow}
\newcommand{\ola}{\overleftarrow}

\addtolength{\oddsidemargin}{-0.7cm}
\addtolength{\textheight}{2.5cm}
\addtolength{\textwidth}{1.4cm}
\addtolength{\topmargin}{-1.5cm}
\renewcommand{\theenumi}{\arabic{enumi}}
\renewcommand{\labelenumi}{\upshape{(\theenumi)}}
%%%%%%%%%%%%%%%%%%%% End of MACRO %%%%%%%%%%%%%%%%%%%%%
%\renewcommand{\baselinestretch}{1.3}

\bfseries\normalfont

\date{}

\begin{document}
\title{A New Approach Towards a Conjecture on Intersecting Three Longest Paths}
\author{Shinya Fujita$^1$,  Michitaka Furuya$^2$, Reza Naserasr$^3$, Kenta Ozeki$^4$}

\maketitle

\noindent\footnotetext[1]{International College of Arts and Sciences, Yokohama City University,  22-2 Seto, Kanazawa-ku, Yokohama 236-0027, Japan; shinya.fujita.ph.d@gmail.com}
\noindent\footnotetext[2]{Department of Mathematical Information Science, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan; michitaka.furuya@gmail.com}
\noindent\footnotetext[3]{CNRS, LRI, UMR8623, Univ. Paris-Sud 11, F-91405 Orsay Cedex, France; reza@lri.fr}
\noindent\footnotetext[4]{National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-Ku, Tokyo 101-8430, Japan and JST, ERATO, Kawarabayashi Large Graph Project, Japan; ozeki@nii.ac.jp}


\begin{abstract}
In 1966, T. Gallai asked whether  every connected graph has a vertex that appears in all longest paths. Since then this question has attracted much attention and many work has been done in this topic. 
One important open question in this area is to ask whether any three longest paths contains a common vertex in a connected graph. 
It was conjectured that the answer to this question is positive. 
In this paper, we propose a new approach in view of distances among longest paths in a connected graph,
 and give a substantial progress towards the conjecture along the idea.   
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}\label{sec1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In \cite{ref5} Gallai asked whether every connected graph has a vertex that appears in all longest paths. This question has attracted much attention and many work has been done around this area of study. 
The answer to this question is false as stated; actually several counterexamples were given in \cite{ref16, ref18, ref21}.  
A graph $G$ is \textit{hypotraceable} if $G$ has no Hamiltonian path but every vertex-deleted subgraph $G-v$ has. 
Note that hypotraceable graphs constitute a large class of counterexamples. 
 Thomassen \cite{ref12} showed that there exist infinitely many planar hypotraceable graphs, meaning that there exist 
 infinitely many counterexamples towards the question. 
 
 Yet there are classes of graphs for which the answer to Gallai's question is positive. 
 To see this, note that, in a tree, all longest paths must contain its center(s). 
 Klav\u{z}ar and Petkov\u{s}ek \cite{ref9} showed that the answer is also positive for split graphs, cacti, and some other classes of graphs. 
 Balister et al. \cite{ref2} obtained a similar result for the class of circular arc graphs. 
 
Regarding Gallai's question, what happens if we consider the intersection of a smaller number of longest paths? 
While we can easily check that every two longest paths share a vertex, it is not known whether every three longest paths also share a vertex. 
In \cite{ref7} it appears as a conjecture, which has originally been asked by Zamfirescu since the 1980s (see \cite{ref22}). 

\begin{con}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{Z}
For every connected graph, any three of its longest paths have a common vertex. 
\end{con}

So far, very little progress has been made on this conjecture. 
Axenovich \cite{ref1} proved that Conjecture~\ref{Z} is true for connected outerplanar graphs, and de Rezende et al. \cite{ref0} proved that Conjecture~\ref{Z} is true for connected graphs in which all nontrivial blocks are Hamiltoninan.  

In this paper, we introduce a new graph parameter in view of distances among longest paths in a connected graph. 
To state this, we give some basic definitions. 
For a graph $G$, let $P$ be a path in $G$, and let $x$ and $y$ be the end-vertices of $P$.
Note that $|V(P)|=1$ if and only if $x=y$.
For $X,Y\subseteq V(G)$, $P$ is called an {\it $X$-$Y$ path} if $V(P)\cap X=\{x\}$ and $V(P)\cap Y=\{y\}$.
Let $u,v\in V(P)$.
We let $uPv$ denote the $\{u\}$-$\{v\}$ path on $P$.
Furthermore, we let $\check{u}Pv=uPv-u$, $uP\check{v}=uPv-v$ and $\check{u}P\check{v}=uPv-\{u,v\}$.

Let $G$ be a connected graph. 
Let $l(G)$ be the length of any longest path in $G$, and let $\L(G)$ be the set of longest paths of $G$; thus $\L(G)=\{P\mid P$ is a path in $G$ with $|V(P)|=l(G)+1\}$. 
For $x,y\in V(G)$ let $d_G(x,y)$ be the distance between $x$ and $y$ in $G$ (i.e., the length of a shortest path joining $x$ and $y$ in $G$). 
Also for a vertex $x\in V (G)$ and a subset $U\subseteq V(G)$, let $d_G(x,U) = \min\{d_G(x,y) \mid y\in U\}$.
For $\P\subseteq \L(G)$, let $f(G,\P)=\min \{\sum_{P\in \P}d_{G}(v,V(P))\mid v\in V(G)\}$. 

Using this graph parameter, we can formulate Conjecture~\ref{Z} as follows.

\begin{con}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{Gallai}
Let $G$ be a connected graph, and let $\P$ be a subset of $\L(G)$ with $|\P|=3$.
Then $f(G,\P)=0$.
\end{con}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

As mentioned before, it is easy to check that any two longest paths of a connected graph have a common vertex. We now give the proof in this context. 

\begin{prop}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{prop1}
Let $G$ be a connected graph, and let $\P$ be a subset of $\L(G)$ with $|\P|=2$.
Then $f(G,\P)=0$.
\end{prop}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\proof
Write $\P=\{P_{1},P_{2}\}$, and for each $i\in \{1,2\}$, let $u_{i}$ and $v_{i}$ be the end-vertices of $P_{i}$.
Since $G$ is connected, $G$ has a $V(P_{1})$-$V(P_{2})$ path $Q$.
Note that $V(P_{1})\cap V(P_{2})\not=\emptyset $ if and only if $|V(Q)|=1$.
For each $i\in \{1,2\}$, write $V(P_{i})\cap V(Q)=\{w_{i}\}$.
We may assume that $|V(u_{i}P_{i}w_{i})|\geq |V(v_{i}P_{i}w_{i})|$ for each $i\in \{1,2\}$.
Then the length of the path $u_{1}P_{1}w_{1}Qw_{2}P_{2}u_{2}$ in $G$ is $(|V(u_{1}P_{1}w_{1})|-1)+(|V(Q)|-1)+(|V(u_{2}P_{2}w_{2})|-1)$.
On the other hand, for each $i\in \{1,2\}$, $|V(u_{i}P_{i}w_{i})|-1\geq ((|V(u_{i}P_{i}w_{i})|-1)+(|V(v_{i}P_{i}w_{i})|-1))/2=(|V(P_{i})|-1)/2=l(G)/2$.
Consequently,
\begin{eqnarray}
\begin{split}
(|V(u_{1}P_{1}w_{1})|-1)&+(|V(u_{2}P_{2}w_{2})|-1)\nonumber \\
&\geq \frac{l(G)}{2}+\frac{l(G)}{2}\nonumber \\
&= l(G)\nonumber \\
&\geq (|V(u_{1}P_{1}w_{1})|-1)+(|V(Q)|-1)+(|V(u_{2}P_{2}w_{2})|-1).\nonumber
\end{split}
\end{eqnarray}
This leads to $|V(Q)|=1$, and hence $V(P_{1})\cap V(P_{2})\not=\emptyset $.
\qed

In this paper, we give an upper bound of $f(G,\P)$ with $|\P|=3$, which is linear in terms of $|V(G)|$.

\begin{thm}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{thm1}
Let $G$ be a connected graph of order $n$, and let $\P$ be a subset of $\L(G)$ with $|\P|=3$.
Then $f(G,\P)\leq (n+6)/13$.
\end{thm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

After proving this bound in Section 2, in the follow-up section we show that to 
prove the conjecture it would be enough to improve our linear bound to any 
nondecreasing sublinear bound.
Namely, we propose an equivalent conjecture towards Conjecture~\ref{Z} in terms of the function $f(G,\P)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proof of Theorem~\ref{thm1}}\label{sec2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We start with some lemmas.

For a set $\P$ of graphs and $P\in \P$, set $X_{\P}(P)=V(P)-(\bigcup _{P'\in \P-\{P\}}V(P'))$.

\begin{lem}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{lem2.1}
Let $G$ be a connected graph of order $n$, and let $\P\subseteq \L(G)$ with $|\P|=3$.
If $f(G,\P)>0$, then $n\geq (3l(G)+\sum _{P\in \P}|X_{\P}(P)|+3)/2$.
\end{lem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\proof
Write $\P=\{P_{1},P_{2},P_{3}\}$.
Since $\bigcap _{1\leq i\leq 3}V(P_{i})=\emptyset $,
\begin{align}
n\geq |\bigcup _{1\leq i\leq 3}V(P)|=\sum _{1\leq i\leq 3}|X_{\P}(P_{i})|+\sum _{1\leq i<j\leq 3}|V(P_{i})\cap V(P_{j})|.\label{eq2.1}
\end{align}
Since $l(G)+1=|V(P_{i})|=|X_{\P}(P_{i})|+\sum _{j\not=i}|V(P_{i})\cap V(P_{j})|$ for each $1\leq i\leq 3$,
\begin{eqnarray}
3l(G)+3 &=& \sum _{1\leq i\leq 3}|X_{\P}(P_{i})|+\sum _{1\leq i\leq 3}(\sum _{j\not=i}|V(P_{i})\cap V(P_{j})|)\nonumber \\
&=& \sum _{1\leq i\leq 3}|X_{\P}(P_{i})|+2\sum _{1\leq i<j\leq 3}|V(P_{i})\cap V(P_{j})|.\label{eq2.2}
\end{eqnarray}
By (\ref{eq2.1}) and (\ref{eq2.2}),
\begin{eqnarray}
n &\geq & \sum _{1\leq i\leq 3}|X_{\P}(P_{i})|+\sum _{1\leq i<j\leq 3}|V(P_{i})\cap V(P_{j})|\nonumber \\
&=& \sum _{1\leq i\leq 3}|X_{\P}(P_{i})|+(3l(G)+3-\sum _{1\leq i\leq 3}|X_{\P}(P_{i})|)/2\nonumber \\
&=& (3l(G)+3+\sum _{1\leq i\leq 3}|X_{\P}(P_{i})|)/2.\nonumber
\end{eqnarray}
Thus we get the desired conclusion.
\qed

For a set $\P$ of three paths and $P\in \P$, let $t_{\P}(P)$ be the number of $V(P_{1})$-$V(P_{2})$ paths on $P$, where $\P-\{P\}=\{P_{1},P_{2}\}$.
If $\P$ consists of three longest paths of a connected graph, then $t_{\P}(P)\geq 1$ for every $P\in \P$ by Proposition~\ref{prop1}.

\begin{lem}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{lem2.2}
Let $G$ be a connected graph, and let $\P\subseteq \L(G)$ with $|\P|=3$.
Then $|X_{\P}(P)|\geq t_{\P}(P)(f(G,\P)-1)$ for each $P\in \P$.
\end{lem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\proof
We may assume that $f(G,\P)\geq 1$.
Write $\P-\{P\}=\{P_{1},P_{2}\}$, and let $\Q$ be the set of $V(P_{1})$-$V(P_{2})$ paths on $P$.
Note that every path in $\Q$ has order at least two and $|\Q|=t_{\P}(P)$.
Let $Q\in \Q$, and let $u$ and $v$ be the end-vertices of $Q$ with $u\in V(P_{1})$ and $v\in V(P_{2})$.
Then $V(Q)\cap X_{\P}(P)=V(Q)-\{u,v\}$.
Since $u\in V(P)\cap V(P_{1})$, $f(G,\P)\leq \sum_{P'\in \P}d_{G}(u,V(P'))=d_{G}(u,V(P_{2}))\leq d_{G}(u,v)\leq |V(Q)|-1$.
Hence $|V(Q)\cap X_{\P}(P)|=|V(Q)|-2\geq f(G,\P)-1$.
Since $Q$ is arbitrary,
\begin{align}
\sum _{Q\in \Q}|V(Q)\cap X_{\P}(P)|\geq t_{\P}(P)(f(G,\P)-1).\label{eq2.3}
\end{align}
Clearly, each vertex in $X_{\P}(P)$ belongs to at most one path in $\Q$.
This together with (\ref{eq2.3}) implies that $|X_{\P}(P)|\geq |\bigcup _{Q\in \Q}(V(Q)\cap X_{\P}(P))|=\sum _{Q\in \Q}|V(Q)\cap X_{\P}(P)|\geq t_{\P}(P)(f(G,\P)-1)$.
\qed

\begin{lem}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{lem2.3}
Let $G$ be a connected graph, and let $\P\subseteq \L(G)$ with $|\P|=3$.
If there exists a path $P\in \P$ with $t_{\P}(P)=1$, then $f(G,\P)=0$.
\end{lem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\proof
Suppose that $f(G,\P)>0$.
Let $u$ and $v$ be the end-vertices of $P$.
Write $\P-\{P\}=\{P_{1},P_{2}\}$, and for each $i\in \{1,2\}$, let $w_{i}$ be the vertex which is contained in $P_{i}$ and the unique $V(P_{1})$-$V(P_{2})$ path on $P$ (see Figure~\ref{fig1}).
We may assume that $|V(uPw_{1})|\leq |V(uPw_{2})|$.
Since $f(G,\P)>0$, $w_{1}\not=w_{2}$, and hence $|V(w_{1}Pv)|>|V(w_{2}Pv)|$.
Furthermore, we may assume that $|V(uPw_{1})|\leq |V(vPw_{2})|$.
Since $l(G)=|V(uPw_{1})|+|V(w_{1}Pv)|-2$,
\begin{eqnarray}
|V(w_{1}Pv)| &>& \frac{|V(w_{1}Pv)|}{2}+\frac{|V(w_{2}Pv)|}{2}\nonumber \\
&=& \frac{l(G)-|V(uPw_{1})|+2}{2}+\frac{|V(w_{2}Pv)|}{2}\nonumber \\
&\geq & \frac{l(G)-|V(vPw_{2})|+2}{2}+\frac{|V(w_{2}Pv)|}{2}\nonumber \\
&=& \frac{l(G)+2}{2}.\label{eq2.4}
\end{eqnarray}
Let $u_{1}$ and $v_{1}$ be the end-vertices of $P_{1}$.
We may assume that $|V(u_{1}P_{1}w_{1})|\geq |V(w_{1}P_{1}v_{1})|$.
Since $l(G)=|V(u_{1}P_{1}w_{1})|+|V(w_{1}P_{1}v_{1})|-2$,
\begin{align}
|V(u_{1}P_{1}w_{1})|\geq \frac{|V(u_{1}P_{1}w_{1})|+|V(w_{1}P_{1}v_{1})|}{2}=\frac{l(G)+2}{2}.\label{eq2.4+}
\end{align}
By (\ref{eq2.4}) and (\ref{eq2.4+}), $|V(u_{1}P_{1}w_{1})|+|V(w_{1}Pv)|-2>(l(G)+2)/2+(l(G)+2)/2-2=l(G)$.
By the assumption that $t_{\P}(P)=1$, the path $\check{w}_{1}Pv$ contains no vertex in $V(P_{1})$.
Hence $P^{(1)}_{1}=u_{1}P_{1}w_{1}Pv$ is a path in $G$ with length $|V(u_{1}P_{1}w_{1})|+|V(w_{1}Pv)|-2>l(G)$, which is a contradiction.
\qed

\begin{figure}
\begin{center}
\input{f1.tex}
\caption{paths in $\P$}
\label{fig1}
\end{center}
\end{figure}

\medbreak\noindent\textit{Proof of Theorem~\ref{thm1}.}\quad
We may assume that $f(G,\P)\geq 1$.
Choose $P\in \P$ so that $t=t_{\P}(P)$ is as small as possible.
Then $t_{\P}(P)\geq 2$ by Lemma~\ref{lem2.3}.
Let $u$ and $v$ be the end-vertices of $P$.
Write $\P-\{P\}=\{P_{1},P_{2}\}$, and let $u_{i}$ and $v_{i}$ be the end-vertices of $P_{i}$ for each $i\in \{1,2\}$.
Let $Q_{1},Q_{2},\cdots ,Q_{t}$ be the $V(P_{1})$-$V(P_{2})$ paths on $P$ which are aligned on $P$ in order of indices with initial point $u$ (i.e. for each $2\leq i\leq t$, the unique $\{u\}$-$V(Q_{i})$ path on $P$ contains $\bigcup _{1\leq j\leq i-1}V(Q_{j})$).
We may assume that the length of the unique $\{u\}$-$V(Q_{1})$ path on $P$ is at least that of the unique $\{v\}$-$V(Q_{t})$ path on $P$.
For each $1\leq i\leq t$ and each $j\in \{1,2\}$, write $V(Q_{i})\cap V(P_{j})=\{w^{(j)}_{i}\}$.
We may assume that $|V(uPw^{(1)}_{1})|\leq |V(uPw^{(2)}_{1})|$.
Let $R$ be a $\{w^{(1)}_{1}\}$-$V(P_{2})$ path on $P_{1}$, and write $V(R)\cap V(P_{2})=\{x\}$.
For each $i\in \{1,2\}$, we may assume that $|V(u_{i}P_{i}w^{(i)}_{1})|\leq |V(u_{i}P_{i}x)|$ (see Figure~\ref{fig2}).

\begin{figure}
\begin{center}
\input{f2.tex}
\caption{paths in $\P$}
\label{fig2}
\end{center}
\end{figure}

Since $w^{(1)}_{1}\in V(P)\cap V(P_{1})$, $f(G,\P)\leq \sum_{P'\in \P}d_{G}(w^{(1)}_{1},V(P'))=d_{G}(w^{(1)}_{1},V(P_{2}))\leq \min \{d_{G}(w^{(1)}_{1},w^{(2)}_{1}),d_{G}(w^{(1)}_{1},x)\}\leq \min \{|V(Q_{1})|-1,|V(R)|-1\}$.
Hence
\begin{align}
|V(Q_{1})|\geq f(G,\P)+1~\mbox{ and }~|V(R)|\geq f(G,\P)+1.\label{eq2.5}
\end{align}

Since $w^{(2)}_{1}Q_{1}\check{w}^{(1)}_{1}$ contains no vertex in $V(P_{1})$, $w^{(2)}_{1}Q_{1}w^{(1)}_{1}Rx$ is a path in $G$.
Furthermore, since $\check{w}^{(2)}_{1}Q_{1}w^{(1)}_{1}P_{1}\check{x}$ contains no vertex in $V(P_{2})$,\\
(i)~$S_{1}=v_{2}P_{2}w^{(2)}_{1}Q_{1}w^{(1)}_{1}R\check{x}$,\\
(ii)~$S_{2}=u_{2}P_{2}w^{(2)}_{1}Q_{1}w^{(1)}_{1}RxP_{2}v_{2}$ and\\
(iii)~$S_{3}=u_{2}P_{2}xRw^{(1)}_{1}Q_{1}\check{w}^{(2)}_{1}$.\\
are paths in $G$ (see Figure~\ref{fig3}).

\begin{figure}
\begin{center}
\input{f3.tex}
\caption{path $S_{i}$}
\label{fig3}
\end{center}
\end{figure}

Since the length of $S_{1}$ is $(|V(v_{2}P_{2}w^{(2)}_{1}|-1)+(|V(Q_{1})|-1)+(|V(w^{(1)}_{1}R\check{x})|-1)$ and $|V(w^{(1)}_{1}R\check{x})|=|V(R)|-1$, we have $(|V(v_{2}P_{2}w^{(2)}_{1})|-1)+(|V(w^{(2)}_{1}P_{2}u_{2})|-1)=|V(P_{2})|-1=l(G)\geq (|V(v_{2}P_{2}w^{(2)}_{1}|-1)+(|V(Q_{1})|-1)+(|V(R)|-2)$.
This together with (\ref{eq2.5}) leads to
\begin{align}
|V(u_{2}P_{2}w^{(2)}_{1})|\geq |V(Q_{1})|+|V(R)|-2\geq 2f(G,\P).\label{eq2.6}
\end{align}
By comparing the length of $P_{2}$ and $S_{2}$ and (\ref{eq2.5}), we have
\begin{align}
|V(w^{(2)}_{1}P_{2}x)|\geq |V(Q_{1})|+|V(R)|-1\geq 2f(G,\P)+1.\label{eq2.7}
\end{align}
By comparing the length of $P_{2}$ and $S_{3}$ and (\ref{eq2.5}), we also have
\begin{align}
|V(xP_{2}v_{2})|\geq |V(Q_{1})|+|V(R)|-2\geq 2f(G,\P).\label{eq2.8}
\end{align}
Therefore
\begin{eqnarray}
l(G) &=& |V(P_{2})|-1\nonumber \\
&=& |V(u_{2}P_{2}w^{(2)}_{1})|+|V(w^{(2)}_{1}P_{2}x)|+|V(xP_{2}v_{2})|-3\nonumber \\
&\geq & 2f(G,\P)+(2f(G,\P)+1)+2f(G,\P)-3\nonumber \\
&=& 6f(G,\P)-2.\label{eq2.9}
\end{eqnarray}

\medskip
\noindent
\textbf{Case 1:} $t_{\P}(P)=2$.

\begin{figure}
\begin{center}
\input{f4.tex}
\caption{path $T$}
\label{fig4}
\end{center}
\end{figure}

Note that $|V(vPw^{(1)}_{2})|\leq |V(vPw^{(2)}_{2})|$.
Since the path $uP\check{w}^{(2)}_{1}$ contains no vertex in $V(P_{2})$, $T=uPw^{(2)}_{1}P_{2}v_{2}$ is a path in $G$ (see Figure~\ref{fig4}).
Since the length of $T$ is $(|V(uPw^{(1)}_{1})|-1)+(|V(Q_{1})|-1)+(|V(w^{(2)}_{1}P_{2}v_{2})|-1)$, $(|V(u_{2}P_{2}w^{(2)}_{1})|-1)+(|V(w^{(2)}_{1}P_{2}v_{2})|-1)=|V(P_{2})|-1=l(G)\geq (|V(uPw^{(1)}_{1})|-1)+(|V(Q_{1})|-1)+(|V(w^{(2)}_{1}P_{2}v_{2})|-1)$.
This together with (\ref{eq2.5}) leads to
\begin{align}
|V(u_{2}P_{2}w^{(2)}_{1})|\geq |V(uPw^{(1)}_{1})|+|V(Q_{1})|-1\geq |V(uPw^{(1)}_{1})|+f(G,\P).\label{eq2.10}
\end{align}
Since the path $\check{w}^{(1)}_{2}P\check{w}^{(1)}_{1}$ contains no vertex in $V(P_{1})$, both $T_{1}=\check{w}^{(1)}_{2}Pw^{(1)}_{1}P_{1}u_{1}$ and $T_{2}=\check{w}^{(1)}_{2}Pw^{(1)}_{1}P_{1}v_{1}$ are paths in $G$ (see Figure~\ref{fig5}).
\begin{figure}
\begin{center}
\input{f5.tex}
\caption{path $T_{i}$}
\label{fig5}
\end{center}
\end{figure}
Since the length of $T_{1}$ is $(|V(\check{w}^{(1)}_{2}Pw^{(1)}_{1})|-1)+(|V(w^{(1)}_{1}P_{1}u_{1})|-1)$, we have $(|V(vPw^{(1)}_{2})|-1)+(|V(w^{(1)}_{2}Pw^{(1)}_{1})|-1)+(|V(w^{(1)}_{1}Pu)|-1)=|V(P)|-1=l(G)\geq (|V(\check{w}^{(1)}_{2}Pw^{(1)}_{1})|-1)+(|V(w^{(1)}_{1}P_{1}u_{1})|-1)$.
Consequently, we have $|V(vPw^{(1)}_{2})|+|V(w^{(1)}_{1}Pu)|\geq |V(w^{(1)}_{1}P_{1}u_{1})|$.
By comparing the length of $P$ and $T_{2}$, we also have $|V(vPw^{(1)}_{2})|+|V(w^{(1)}_{1}Pu)|\geq |V(w^{(1)}_{1}P_{1}v_{1})|$.
Hence
\begin{eqnarray}
l(G) &=& |V(P_{1})|-1\nonumber \\
&=& |V(u_{1}P_{1}w^{(1)}_{1})|+|V(w^{(1)}_{1}P_{1}v_{1})|-2\nonumber \\
&\leq & 2(|V(vPw^{(1)}_{2})|+|V(w^{(1)}_{1}Pu)|)-2.\label{eq2.11}
\end{eqnarray}
Recall that the length of the unique $\{u\}$-$V(Q_{1})$ path on $P$ (i.e. $uPw^{(1)}_{1}$) is at least that of the unique $\{v\}$-$V(Q_{2})$ path on $P$ (i.e. $vPw^{(1)}_{2}$).
Hence $|V(uPw^{(1)}_{1})|\geq |V(vPw^{(1)}_{2})|$.
By (\ref{eq2.11}), $l(G)\leq 2(|V(vPw^{(1)}_{2})|+|V(w^{(1)}_{1}Pu)|)-2\leq 4|V(uPw^{(1)}_{1})|-2$, and so $|V(uPw^{(1)}_{1})|\geq (l(G)+2)/4$.
This together with (\ref{eq2.10}) implies that
\begin{align}
|V(u_{2}P_{2}w^{(2)}_{1})|\geq \frac{l(G)+2}{4}+f(G,\P).\label{eq2.12}
\end{align}
By (\ref{eq2.7}), (\ref{eq2.8}) and (\ref{eq2.12}),
\begin{eqnarray}
l(G) &=& |V(P_{2})|-1\nonumber \\
&=& |V(u_{2}P_{2}w^{(2)}_{1})|+|V(w^{(2)}_{1}P_{2}x)|+|V(xP_{2}v_{2})|-3\nonumber \\
&\geq & (\frac{l(G)+2}{4}+f(G,\P))+(2f(G,\P)+1)+2f(G,\P)-3\nonumber \\
&=& \frac{l(G)-6}{4}+5f(G,\P),\nonumber
\end{eqnarray}
and so
\begin{align}
l(G)\geq \frac{20f(G,\P)-6}{3}.\label{eq2.13}
\end{align}
By the choice of $P$, $t_{\P}(P')\geq 2$ for every $P'\in \P$.
By Lemma~\ref{lem2.2}, $\sum _{P'\in \P}|X_{\P}(P')|\geq \sum _{P'\in \P}t_{\P}(P')(f(G,\P)-1)\geq 6(f(G,\P)-1)$.
This together with Lemma~\ref{lem2.1} and (\ref{eq2.13}) implies that
\begin{eqnarray}
n &\geq & \frac{3l(G)+\sum _{P'\in \P}|X_{\P}(P')|+3}{2}\nonumber \\
&\geq & \frac{3\cdot \frac{20f(G,\P)-6}{3}+6(f(G,\P)-1)+3}{2}\nonumber \\
&=& \frac{26f(G,\P)-9}{2},\nonumber
\end{eqnarray}
and hence $f(G,\P)\leq (2n+9)/26$.

\medskip
\noindent
\textbf{Case 2:} $t_{\P}(P)\geq 3$.

By the choice of $P$, $t_{\P}(P')\geq 3$ for every $P'\in \P$.
By Lemma~\ref{lem2.2}, $\sum _{P'\in \P}|X_{\P}(P')|\geq \sum _{P'\in \P}t_{\P}(P')(f(G,\P)-1)\geq 9(f(G,\P)-1)$.
This together with Lemma~\ref{lem2.1} and (\ref{eq2.9}) implies that
\begin{eqnarray}
n &\geq & \frac{3l(G)+\sum _{P'\in \P}|X_{\P}(P')|+3}{2}\nonumber \\
&\geq & \frac{3(6f(G,\P)-2)+9(f(G,\P)-1)+3}{2}\nonumber \\
&=& \frac{27f(G,\P)-12}{2},\nonumber
\end{eqnarray}
and hence $f(G,\P)\leq (2n+12)/27$.

This completes the proof of Theorem~\ref{thm1}.
\qed


To conclude this section, we propose the following conjecture. 


\begin{con}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{con2}
Let $G$ be a connected graph, and let $\P\subseteq \L(G)$ with $|\P|=3$.
If there exists a path $P\in \P$ with $t_{\P}(P)=2$, then $f(G,\P)=0$.
\end{con}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

If Conjecture~\ref{con2} is true, then we can improve the upper bound of $f(G,\P)$ in Theorem~\ref{thm1} to $(2n+12)/27$ (by the argument in the proof of Theorem~\ref{thm1}).













\section{Bounding the value of $f(G,\P)$ by a sublinear function}



A function $g$ is \textit{sublinear}
if $\lim_{n \rightarrow +\infty} \frac{g(n)}{n} = 0$. 
It follows from the definition that, if $g$ is sublinear, then for any two constants $c_0, c_1$, we have $g(c_0t+c_1)<t$ for any large $t$. 
%A function $g$ is \textit{non-negative}
%if $g(n) \geq 0$ for any $n$.
Here we pose the following new conjecture,
which concerns Conjecture \ref{Gallai}.
Although Conjecture \ref{sublinear} is 
seemingly weaker than Conjecture \ref{Gallai},
we will show that 
Conjecture~\ref{sublinear} is indeed equivalent with Conjecture~\ref{Gallai}.


\begin{con}
\label{sublinear}
There exists a sublinear non-decreasing function $g$ 
such that 
for every connected graph $G$ of order $n$
and every subset $\P$ of $\L(G)$ with $|\P|=3$,
$f(G, \P) \leq g(n)$.
\end{con}

To prove that this seemingly weaker conjecture is equivalent to 
Conjecture~\ref{Gallai}, we first show that for a given graph $G$ with a set 
$\{P_1,P_2, P_3\}$ of three longest paths one can choose a subdivision of $G$ so that 
subdivisions of $P_i$'s $i=1,2,3$ are the new longest paths and show that the 
minimum distance from these three subdivided paths in the subdivided graph 
grows linearly in the order of subdivision. For the exact statement we introduce 
the following notation.

Let $G$ be a connected graph and let $\mathcal P=\{P_1,P_2, P_3\}$  be a set of three 
longest paths. Let $G'$ be obtained by adding a new edge to each end-vertex 
of  $P_i$'s, $i=1,2,3$; thus, minimum of two and maximum of six new vertices and 
edges are added. Let $P'_i$, $i=1,2,3$ be the path corresponding to $P_i$ with two 
new edges at the two ends.  We define $G^t$ to be the graph obtained from $G'$ 
by subdividing 
each edge $t$ times. Let $P^t_i$, $i=1,2,3$ be the corresponding path of $P'_i$ 
in $G^t$.  We write 
$\mathcal P^{t}= \{P^t_1,P^t_2, P^t_3\}$. Also, let $V_{f(G,\P)}=\{v\in V(G)\mid \sum_{P\in \P}d_{G}(v,V(P))=f(G,\P)\}$.

We have the following proposition.

\begin{prop}
 Given a connected graph $G$ and a set $\mathcal P=\{P_1,P_2, P_3\}$ of three longest 
paths, the set $\mathcal P^{t}= \{P^t_1,P^t_2, P^t_3\}$ is a set of three 
longest paths of $G^t$. Furthermore, $f(G^t, \P^t)=(t+1)f(G, \P)$.
\end{prop}


\proof
 The first assertion is easy to check. To prove the second assertion, we show that a 
vertex  of $V_{f(G^t,\mathcal{P}^t)}$ could be chosen as 
an original vertex of $G$. The assertion then would follow, as the vertex of $G$ attaining  
the distance sum $f(G, \P)$ of $\P$ satisfies $(t+1)f(G, \P)$ for the distance sum of $\P^t$ in $G^t$ as well.

Now let $u$ be a vertex attaining the distance sum $f(G^t, \P^t)$ from $\P^t$. 
It is easy to check that $u$ is not an end-vertex of $P^t_i$ for any $i$. If $u\in 
V(G)$, then we have nothing to prove. Otherwise $u$ is a new vertex 
subdividing an edge, say $xy$, of $G$. If all the shortest paths from $u$ to 
$P^t_i$, $i=1,2,3$, go through $x$ (or $y$) then replacing $u$ by $x$ (or $y$) provides a 
smaller distance sum than $f(G^t, \P^t)$, a contradiction. Thus we may assume, without loss of 
generality, that two of the shortest paths from $u$ to $P^t_i$ go through $x$ 
and the third one goes through $y$. 
In such a case again by replacing $u$ by $x$ we 
will 
have a smaller distance sum than $f(G^t, \P^t)$, a contradiction. 
We note that if $u$ belongs to one or two
of these paths then so are $x$ and $y$, thus this would not affect the 
argument. The contradiction proves that $u$ must 
be a vertex of $G$ and we have $f(G^t, \P^t)=(t+1)f(G, \P)$.
\qed

Keeping the above proposition in mind, we can prove the following theorem. 

\begin{thm}\label{order}
Conjecture~\ref{Gallai} is true if and only if 
Conjecture~\ref{sublinear} is true.
\end{thm}


\proof
The ``only if'' part is trivial,
and hence we only show the ``if'' part.

Suppose that $G$ together with $\P =\{P_1,P_2, P_3\}$ is a counterexample for 
Conjecture~\ref{Gallai}, i.e.,  $f(G, \P)\geq 1$. The subgraph of $G$ 
induced by edges and vertices of $P_1,P_2,P_3$  is also a
counterexample (where $\P$ is also a set of non-intersecting three longest 
paths). Note that, in view of Proposition~\ref{prop1}, such a subgraph is connected.  
Thus we may assume from the start that vertices and edges of $G$ are union of 
vertices and edges of $P_1,P_2,P_3$. Let $n_0$ be the number of vertices of $G$. 
Since $G$ is union of three paths each of length at most $n_0-1$, we conclude 
that $G$ has at most $3(n_0-1) (<3(n_0+1))$ edges. 

%Since $G^t$ is obtained from subdividing edges of $G$ (each edge exactly $t$ 
%times) it has at most $n_0+3(n_0+1)t$ vertices.  
Hence, by the construction of $G^t$, we have $|V(G^t)|\leq n_0+3(n_0+1)t+6$. 
On the other hand, we have 
$f(G^t, \P^t)=(t+1)f(G, \P)\geq t$.  Hence for constants $c_0=3n_0+3$ and $c_1=n_0+6$
we have $g(c_0t+c_1)\geq t$ (because $g$ is non-decreasing). 
However, this contradicts the fact that $g$ is a sublinear function. 
\qed



% 
% 
% Suppose that 
% there exists a sublinear non-decreasing function $g$ 
% such that 
% for every connected graph $G$ of order $n$
% and every subset $\P$ of $\L(G)$ with $|\P|=3$,
% $f(G, \P) \leq g(n)$.
% %If $g$ is not non-increasing,
% %then we can replace $g$ with 
% %Let $\overline{g}(n) = \max_{1 \leq n' \leq n} g(n')$.
% %Note that $\overline{g}$ is a non-decreasing function,
% %on the set of positive integers.
% %Notice also that
% %and 
% %for all $n$,
% %$f(G, \P) \leq \overline{g}(n)$ if $f(G, \P) \leq g(n)$,
% %$g(n) \leq \overline{g}(n)$,
% %which implies that $\overline{g}$ is also non-negative.
% %We can easily check that 
% %$\overline{g}$ is also sublinear.
% 
% 
% 
% Let $G$ be a connected graph of order $n$,
% and let $\P$ be a subset of $\L(G)$ with $|\P|=3$.
% Write $\P=\{P_{1},P_{2}, P_{3}\}$,
% and for $i \in \{1,2,3\}$, 
% let $u_{i}$ and $v_{i}$ be the end-vertices of $P_{i}$.
% We will show that $f(G, \P) = 0$.
% If $n \leq 3$,
% then we can easiliy show that 
% $f(G, \P) = 0$.
% Hence we may assume that $n \geq 4$.
% %To do that,
% %we construct the new graph $G^*$ from $G$ 
% %with three longest paths, and use the function $\overline{g}$ to it.
% 
% %Since $\overline{g}$ is sublinear,
% Since $g$ is sublinear and non-decreasing,
% we can take an integer $t^*$
% such that 
% \begin{eqnarray}
% \frac{g(t^*)}{t^*} \leq \frac{1}{2n^2}
% \label{sublinearfirst}
% \end{eqnarray}
% and $t^*$ is multiple of $n^2$ but not multiple of $2n^2$.
% Let 
% \begin{eqnarray}
% t = \frac{t^*}{n^2}.
% \label{sublinearsecond}
% \end{eqnarray}
% Note that $t$ is an odd number.
% 
% 
% We obtain the new graph $G^*$ from $G$ by 
% %\begin{enumerata}{
% adding a pendant edge to each of the vertices $u_1,u_2,u_3,v_1,v_2$ and $v_3$,
% say $u_iu_i^*$ and $v_iv_i^*$ for $i \in \{1,2,3\}$,
% and then
% %replacing all edges by pairwise disjoint paths of length $t$.
% subdividing all edges $(t-1)$ times.
% In other words,
% $G^*$ is obtained from $G$ by replacing each edge by a path of length $t$
% after adding the pendant edges $u_iu_i^*$ and $v_iv_i^*$ for $i \in \{1,2,3\}$.
% Let $n^*$ be the order of $G^*$.
% Since $n \geq 4$,
% note that 
% %
% \begin{eqnarray}
% n^* = n + 6 + (t-1)(|E(G)| +6) 
% \leq n + 6 + (t-1)\Big(\frac{n(n-1)}{2} +6 \Big) \leq tn^2.
% \label{sublinearthird}
% \end{eqnarray}
% For $i \in \{1,2,3\}$,
% let $P_i^*$ be the path in $G^*$
% corresponding to the path $u_i^*u_iP_iv_iv_i^*$.
% (Indeed, $P_i^*$ is obtained from the path $u_i^*u_iP_iv_iv_i^*$
% by subdividing all edges $(t-1)$ times.)
% We first show the following claim.
% 
% \begin{claim}
% \label{Pi'longest}
% %For $1 \leq i \leq 3$,
% For $i \in \{1,2,3\}$,
% $P_i^*$ is a longest path in $G^*$.
% \end{claim}
% 
% \proof
% Note that $|V(P_i^*)| = t (|V(P_i)|+1) +1$.
% Thus,
% $P_1^*, P_2^*$ and $P_3^*$ has the same length.
% Suppose that there exists a path $Q^*$ in $G^*$ 
% with $|V(Q^*)| > |V(P_1^*)|$.
% %Then $Q'$ must pass through $t (|V(P_i)|+1) + 1$ edges in $G'$.
% Let $u_{Q}^*$ and $v_{Q}^*$ be the end-vertices of $Q^*$,
% and 
% let $u_{Q}$ and $v_{Q}$ be the vertices in $Q^*$ 
% such that both $u_{Q}$ and $v_{Q}$ are
% vertices in the original graph $G$,
% $u_{Q}$ is closest to $u_{Q}^*$ in $Q^*$,
% and 
% $v_{Q}$ is closest to $v_{Q}^*$ in $Q^*$.
% By the choice of $u_{Q}$ anf $v_{Q}$
% and the construction of $G^*$,
% $|V(u_{Q}^*Q^*u_{Q})| \leq t+1$
% and $|V(v_{Q}Q^*v_{Q}^*)| \leq t+1$.
% Let $Q$ be the path in $G$
% that corresponds to $u_{Q}Q^*v_{Q}$.
% Then we have 
% \begin{eqnarray*}
% |V(Q)| &=& \frac{|V(u_{Q}Q^*v_{Q})|-1}{t} +1 \\
% &=& \frac{|V(Q^*)| - (|V(u_{Q}^*Q^*u_{Q})|-1) - (|V(v_{Q}Q^*v_{Q}^*)|-1) -1}{t} +1 \\
% &\geq& \frac{ t (|V(P_1)|+1) +2 - 2t-1}{t}+1 \\
% &=& \frac{ t |V(P_1)| -t +1}{t}+1 \\
% &>& |V(P_1)|,
% %+ \frac{1}{t},
% \end{eqnarray*}
% which contradicts the assumption that
% $P_1$ is a longest path in $G$.
% \qed
% 
% By Claim \ref{Pi'longest},
% all of $P_1^*, P_2^*$ and $P_3^*$ are longest paths in $G^*$.
% Then by the condition of $g$,
% we have $f(G^*, \P^*) \leq g(n^*)$,
% where $\P^* = \{P_1^*, P_2^*, P_3^*\}$.
% %Since $t = \frac{t^*}{n^2}$ and $g(t^*),
% %we have that $
% Since $g$ is non-decreasing,
% this together with inequalities (\ref{sublinearfirst})--(\ref{sublinearthird})
% implies that
% $$
% f(G^*, \P^*) \ \leq \ g(n^*) 
% \ \leq \ g(tn^2) \ = \ g(t^*) 
% \ \leq \ \frac{t^*}{2n^2} \ = \ \frac{tn^2}{2n^2} \ = \ \frac{t}{2}.
% $$
% 
% Since $t$ is an odd number,
% we have $f(G^*, \P^*) \leq \frac{t-1}{2}$.
% %$\sum_{P^*\in \P^*}d_{G^*}(v^*,V(P^*)) \leq \frac{t-1}{2}$.
% %
% Hence
% there exists a vertex $v^*$ in $G^*$
% such that 
% $\sum_{P^*\in \P^*}d_{G^*}(v^*,V(P^*)) \leq \frac{t-1}{2}$.
% %Since $t$ is an odd number,
% %$\sum_{P^*\in \P^*}d_{G^*}(v^*,V(P^*)) \leq \frac{t-1}{2}$.
% Let $v$ be the vertex of the original graph $G$
% such that $v$ is closest to $v^*$ in $G^*$.
% By the construction of $G^*$,
% for any vertex $u$ of the original graph $G$
% with $u \not= v$,
% we have  
% $d_{G^*}(v^*,u) \geq t - d_{G^*}(v^*,v) \geq \frac{t+1}{2}$.
% 
% Suppose that
% for some $i$ with $i \in \{1,2,3\}$,
% $v$ is not contained in $P_i^*$,
% say $P_1^*$ by symmetry.
% By the construction of $G^*$,
% no vertices between $v$ and $v^*$ are contained in $P_1^*$.
% Hence $d_{G^*}(v^*,V(P_1^*)) \geq \min_{u \in V(G) -\{v\}} d_{G^*}(v^*,u)
% \geq \frac{t+1}{2}$.
% However,
% this implies that
% $$\sum_{P^*\in \P^*}d_{G^*}(v^*,V(P^*)) \geq d_{G^*}(v^*,V(P_1^*)) 
% \geq \frac{t+1}{2},$$
% contradicting the choice of $v^*$.
% 
% Therefore,
% $v$ is contained in 
% $P_i^*$ for all $i$ with $i \in \{1,2,3\}$.
% By the construction of $P_1^*,P_2^*$ and $P_3^*$,
% $v$ is contained in 
% $P_i$ for all $i$ with $i \in \{1,2,3\}$.
% Hence $f(G,\P) = 0$.
% This completes the proof of Theorem \ref{order}.
% \qed





In conclusion, Theorem \ref{order} tells us that giving a substantial improvement on the magnitude of the upper bound of $f(G,\P)$ in Theorem~\ref{thm1} settles the longstanding conjecture on intersecting three longest paths in a connected  graph. \\

\noindent\textbf{Acknowledgments}

We would like to thank Dr.Valentin Borozan for a fruitful discussion concerning this paper. 
The first author would like to thank the laboratory LRI of the University Paris South and Digiteo foundation for their generous hospitality.  He was able to carry out part of this research during his visit there. Also, the first author's research is supported by the Japan Society for the Promotion of Science Grant-in-Aid for Young Scientists (B) (20740095).  
The second author's research is in part supported by
the Japan Society for the Promotion of Science Grant-in-Aid for Young Scientists (B) (26800086).  
The fourth author's research is in part supported by
the Japan Society for the Promotion of Science Grant-in-Aid for Young Scientists (B) (25871053),
and by Grant for Basic Science Research Projects from The Sumitomo Foundation. 

 

\begin{thebibliography}{99}

\bibitem{ref1} M. Axenovich, When do three longest paths have a common vertex? Discrete Math. Algorithms Appl. 1 (2009) 115-120. 

\bibitem{ref2} P. Balister, E. Gy\"{o}ri, J. Lehel, R. Schelp, Longest paths in circular arc graphs, Combin. Probab. Comput. 13 (2004) 311-317. 

\bibitem{ref0} S. F. de Rezende, C. G. Fernandes, D. M. Martin, Y. Wakabayashi, Intersecting longest paths, Discrete Math. 313 (2013) 1401-1408. 

\bibitem{ref5} P. Erd\"{o}s, G. Katona (Eds.), Theory of Graphs, Proceedings of the Colloquium Held at Tihany, Hungary, 1966, Academic Press, New York, 1968, Problem 4 (T. Gallai), p. 362. 

\bibitem{ref7} J. Harris, J. Hirst, M. Mossinghoff, Combinatorics and Graph Theory, in: Undergraduate Texts in Mathematics, Springer, 2008. 

\bibitem{ref9} S. Krav\u{z}ar, M. Petkov\u{s}ek, Graphs with nonempty intersection of longest paths, Ars Combin. 29 (1990) 43-52. 

\bibitem{ref12} C. Thomassen, Planer and infinite hypohamiltonian and hypotraceable graphs, Discrete Math. 14 (1976) 377-389. 

\bibitem{ref16} H. Walther, \"{U}ber die Nichtexistenz eines Knotenpunktes, durch den alle l\"{a}ngsten Wege eines Graphen gehen, J. Combin. Theory 6 (1969) 1-6. 

\bibitem{ref18} H. Walther, H. J. Voss, \"{U}ber Kreise in Graphen, VEB Deutscher Verlag der Wissenschaften, 1974. 

\bibitem{ref21} T. Zamfirescu, On longest paths and circuits in graphs, Math. Scand. 38 (1976) 211-239. 

\bibitem{ref22} T. Zamfirescu, Intersecting longest paths or cycles: a short survey, An. Univ. Craiova Ser. Mat. Inform. 28 (2001) 1-9. 

\end{thebibliography}





\end{document}
1503.01219.extracted_bib
{ref1 M. Axenovich, When do three longest paths have a common vertex? Discrete Math. Algorithms Appl. 1 (2009) 115-120.
1503.01219.extracted_bib
{ref2 P. Balister, E. Gy\"{ori, J. Lehel, R. Schelp, Longest paths in circular arc graphs, Combin. Probab. Comput. 13 (2004) 311-317.
1503.01219.extracted_bib
{ref0 S. F. de Rezende, C. G. Fernandes, D. M. Martin, Y. Wakabayashi, Intersecting longest paths, Discrete Math. 313 (2013) 1401-1408.
1503.01219.extracted_bib
{ref5 P. Erd\"{os, G. Katona (Eds.), Theory of Graphs, Proceedings of the Colloquium Held at Tihany, Hungary, 1966, Academic Press, New York, 1968, Problem 4 (T. Gallai), p. 362.
1503.01219.extracted_bib
{ref7 J. Harris, J. Hirst, M. Mossinghoff, Combinatorics and Graph Theory, in: Undergraduate Texts in Mathematics, Springer, 2008.
1503.01219.extracted_bib
{ref9 S. Krav\u{zar, M. Petkov\u{sek, Graphs with nonempty intersection of longest paths, Ars Combin. 29 (1990) 43-52.
1503.01219.extracted_bib
{ref12 C. Thomassen, Planer and infinite hypohamiltonian and hypotraceable graphs, Discrete Math. 14 (1976) 377-389.
1503.01219.extracted_bib
{ref16 H. Walther, \"{Uber die Nichtexistenz eines Knotenpunktes, durch den alle l\"{angsten Wege eines Graphen gehen, J. Combin. Theory 6 (1969) 1-6.
1503.01219.extracted_bib
{ref18 H. Walther, H. J. Voss, \"{Uber Kreise in Graphen, VEB Deutscher Verlag der Wissenschaften, 1974.
1503.01219.extracted_bib
{ref21 T. Zamfirescu, On longest paths and circuits in graphs, Math. Scand. 38 (1976) 211-239.
1503.01219.extracted_bib
{ref22 T. Zamfirescu, Intersecting longest paths or cycles: a short survey, An. Univ. Craiova Ser. Mat. Inform. 28 (2001) 1-9.