I am trying to prove the graph-theoretic generalization of the following geometric observation:
let $ \mathbb{P}$ be a finite set of distinct points in the Euclidean plane and $ card\left(CH\left(\mathbb{P}\right)\right)\ge4$ , where $ CH\left(\mathbb{P}\right)\subseteq\mathbb{P}$ denotes the set of points constituting to the convex hull of $ \mathbb{P}$ , then the following observation can be made:
If
- $ G’$ is the planar straight-line embedding of a connected graph,
- $ a,b,c,d$ are 4 vertices, whose images $ a’,b’,c’,d’$ constitute to $ CH\left(\mathbb{P}\right)$
- The straight-line segments $ \left(a’,c’\right)$ and $ \left(b’,d’\right)$ intersect in an inner point,
Then
the images of every pair of vertex-disjoint paths connecting $ a$ with $ c$ and $ b$ with $ d$ contain at least one pair of edges $ e_{ij}\in path\left(a,c\right)$ , $ e_{hk} \in path\left(b,d\right)$ , whose images $ e_{ij}’$ and $ e_{hk}’$ intersect in a point, that is an inner point of at least one of the images but is an element of both closed line segments.
“Translation” to the purely graph-theoretic setting:
- let $ G\left(V,E,W\right)$ be a complete, finite, symmetric and weighted graph with at least 4 vertices. The edge-weights shall have the property, that they allow a strict ordering of the weights of the three perfect matchings of every subgraph induced by a quadruplet of the vertices: $ \lbrace a,b,c,d\rbrace\subseteq V\implies w\left(e_{ab}\right)+w\left(e_{cd}\right)\ \lt\ w\left(e_{ad}\right)+w\left(e_{bc}\right)\ \lt\ w\left(e_{ac}\right)+w\left(e_{bd}\right)$ (w.l.o.g.)
- a pair $ (e_{ac},e_{bd})$ of non-adjacent edgesshall be called “crossing“, iff $ w\left(e_{ab}\right)+w\left(e_{cd}\right)\ \le\ w\left(e_{ad}\right)+w\left(e_{bc}\right)\ \lt\ w\left(e_{ac}\right)+w\left(e_{bd}\right)$ (that is the graph-theoretic generalization of intersecting edges)
- $ \chi\left(e_{ac}\right) := \lbrace e_{ij}| \lbrace i,j\rbrace\subset V\setminus\lbrace a,c\rbrace\quad\wedge\quad w\left(e_{ab}\right)+w\left(e_{cd}\right)\ \le\ w\left(e_{ad}\right)+w\left(e_{bc}\right)\ \lt\ w\left(e_{ac}\right)+w\left(e_{bd}\right)\rbrace$ shall be the set of all edges, that are crossing $ e_{ab}$
- an edge $ e_{ab}$ shall be called a “generalized diagonal” iff $ G\setminus\lbrace a,b,\chi\left(e_{ab}\right)\rbrace\rbrace$ is disconnected (note however, that only the edges of $ \chi\left(e_{ac}\right)$ are removed, whereas the adjacent vertices remain in $ G$ ).
Conjecture:
if $ e_{ac}$ and $ e_{bd}$ are a pair of non-adjacent generalized diagonals (as defined above), then every pair of vertex-disjoint paths $ \left(path\left(a,c\right), path\left(b,d\right)\right)$ contains a pair $ e_{ij}\in path\left(a,c\right)$ and $ e_{hk}\in path\left(b,d\right)$ of crossing edges.Question: can the truth of the conjecture be decided by either providing a graph-theoretic proof or a counterexample?
A proof would preferable to me, no matter, whether it is affirmative or not.
Background of the question: The reason, why I am interested in the truth of the conjecture is related to the TSP problem. If the conjecture could be proven in the affirmative way, then it would be possible to identify quadruplets of vertices, that appear in the optimal tour through all points in the same order as in the shortest tour through that quadruplet of vertices, namely if those 4 vertices are adjacent to two crossing generalized diagonals of $ G$ ; that in turn would reduce the number of candidate permutations, that could represent the optimal tour, by a constant factor, because then provably only one of the three possible tours through the quadruplet of vertices can resemble their relative order in the optimal tour.