Intersecting longest paths in chordal graphs

If $P$ has an end vertex in $X$ or contains an edge of $X$ but $v\in X$ is not in $P$, we could extend $P$ to contain $v$ either by adding an edge from the end vertex to $v$, or by replacing an edge of $P$ in $X$ with a 2-edge path containing $v$. Since $P$ is a detour, this is a contradiction. ∎

Suppose otherwise for the sake of a contradiction, that is, there exist detours $P$ and $Q$ satisfying the three properties but also $(P\cap X)\cap(Q\cap X)=\emptyset$. Note that since neither $P$ nor $Q$ end in $X$ and since every path has two ends, it follows $f(P,N)=f(Q,N)$ also. We construct a path $P_{M}$ as follows:

• •

  Consider the graph $G-N$ and the path $P$ inside this graph. Since $P$ intersects $N$, $G-N$ will not contain all of $P$. It is possible that $P-N$ is a set of subpaths of $P$, and as such the number of end vertices of $P-N$ may not be two. However note that the number of end vertices of the subpaths in $P-N$ that are contained in $M$ is still $f(P,M)$; all other end vertices must be in $X$. Since $P$ enters $N$, there is at least one end vertex in $X$; if $f(P,M)\neq 1$ then there are at least two end vertices in $X$ (as exactly one end vertex only occurs when $P$ starts in $M$ and ends in $N$).

• •

  Since $X$ is a clique, we can join the subpaths of $P-N$ together using edges of $X$ to create one long path. Call this $P_{M}$. Note again that $f(P_{M},M)=f(P,M)$. If $f(P,M)=0$ then $P_{M}$ has two end vertices in $X$, if $f(P,M)=1$ then $P_{M}$ has one end vertex in $X$, and if $f(P,M)=2$ then $P_{M}$ has no end vertices in $X$ but since $P$ enters $N$ at least one edge of $X$ is in $P_{M}$.

Construct $P_{N},Q_{M}$ and $Q_{N}$ equivalently. Note that since $P\cap Q\cap X=\emptyset$, it follows $P_{M}\cap Q_{N}=\emptyset$ and $Q_{M}\cap P_{N}=\emptyset$. Also note $f(P_{M},M)+f(Q_{N},N)=f(P,M)+f(Q,N)=f(P,M)+f(P,N)=2$, and also $f(Q_{M},M)+f(P_{N},N)=2$. We now construct a new path $I$. If $f(P_{M},M)=f(Q_{N},N)=1$, then create $I$ by linking the endvertex of $P_{M}$ in $X$ and the endvertex of $Q_{N}$ in $X$ via an edge of $X$. Since $P_{M}\cap Q_{N}=\emptyset$, $I$ will be a path. Alternatively without loss of generality $f(P_{M},M)=0$ and $f(Q_{N},N)=2$. Now create $I$ by deleting an edge of $Q_{N}$ in $X$ and attaching these new end vertices to the two end vertices of $P_{M}$ in $X$. Again this will be a path. Also create a second path $I^{\prime}$ in the same way using $Q_{M}$ and $P_{N}$. Now every vertex of $P$ and $Q$ is in $I\cup I^{\prime}$. However, let $v$ be a vertex of $P\cap X$. The vertex $v$ is in $P_{M}$ and $P_{N}$ and so is in both $I$ and $I^{\prime}$. Thus $|I|+|I^{\prime}|>|P|+|Q|$. But since $P,Q$ have maximum length, $|I|+|I^{\prime}|\leq|P|+|Q|$, a contradiction. ∎

Suppose no central clique exists. Fix a tree decomposition $T$ of $G$ such that each bag is a clique and such that for any two adjacent bags $X$ and $Y$ neither $X\subseteq Y$ nor $Y\subseteq X$. (The first property follows from $G$ being a chordal graph, and the second is achieved by contracting an edge in the tree decomposition whenever the property is violated.) We construct a set of directed edges $D$ with one going out of each bag $B$ as follows:

• •

  If $B$ is a total clique, then since $B$ is not a central clique, there must be at least one small touching detour, and all small touching detours have the same home component, which we call $C$. Direct the arc from $B$ towards the subtree of $T-B$ containing $C$.

• •

  If $B$ is a non-total clique, there is some detour $P$ that does not intersect $B$, and so there is a component $C$ of $G-B$ such that $P\subseteq C$. The component $C$ is entirely within a single subtree of $T-B$, and so we construct an arc from $B$ towards its neighbour in said subtree. Note that even if several detours do not intersect $B$, they must be inside the same component since any two detours intersect, and so our arc is well-defined.

Using the bags of $T$ as nodes and the directed edges $D$ we construct a directed graph where the underlying graph is acyclic and every node has outdegree exactly one. Thus there exists at least one 2-cycle. Let $e$ be the underlying edge of the tree-decomposition corresponding to a $2$-cycle, and label the bags at the end vertices $B$ and $B^{\prime}$. The edge $e$ splits $T$ into two sides, which we label left and right such that $B$ is on the left and $B^{\prime}$ is on the right.

There are now three possibilities to consider. Firstly, suppose that $B$ and $B^{\prime}$ are both non-total cliques. So there exists a detour $P$ that does not intersect $B$ and is entirely on the right, and a detour $Q$ that does not intersect $B^{\prime}$ and is entirely on the left. But then $P\cap Q=\emptyset$, which cannot occur as detours pairwise intersect.

Secondly, suppose that $B$ and $B^{\prime}$ are both total cliques. Let $P$ be a small touching detour with respect to $B$, which will have its home component to the right of $e$. Label the home component of $P$ by $C$. Let $Q$ be a small touching detour with respect to $B^{\prime}$ with its home component to the left of $e$. Define $X=B\cap B^{\prime}$. Suppose $P$ contains a vertex $v$ in $B-X$. Now every vertex of $P$ is contained within $B$ or $C$, but $v$ has no neighbours in $C$ as $v$ and $C$ are separated by $X$. Thus, since $v$ is incident to some edge in $P$, the vertex $u$ at the other end of this edge must be in $B$, and so all of $B$ is in $P$ by Proposition 1. Since $P$ is small with respect to $B$, it follows $B$ is a central clique of type 3. Hence $P$ does not visit $B-X$, and similarly $Q$ does not visit $B^{\prime}-X$. Thus both $P$ and $Q$ are small and touching with respect to the clique-cut $X$. The detours $P,Q$ still have different home components (to the right and left of $e$ respectively) and so $X$ is a central clique of type 2.

Thirdly, suppose (without loss of generality) that $B$ is total and $B^{\prime}$ is non-total. Let $P$ be a small touching detour with respect to $B$, which thus has its home component to the right of $e$. Let $Q$ be a detour that does not intersect $B^{\prime}$ (since it is non-total). Note $Q$ intersects $B$, and is entirely to the left of $e$. Again, let $X:=B\cap B^{\prime}$. As in the previous case, if $P$ contains a vertex $v$ in $B-X$, then all of $B$ is in $P$ and $B$ is a central clique of type 3. Hence we suppose that $P$ does not intersect $B-X$. However, $P$ and $Q$ must intersect, and $Q$ does not intersect $B^{\prime}$ and therefore does not intersect $X$, which leaves nowhere for the two detours to intersect. This gives our final contradiction. ∎

Let $R$ be a detour in $G$. There are two cases to consider: either $R$ is large with respect to $X$ or $R$ is small with respect to $X$. If $R$ is large with respect to $X$, then $|R\cap X|\geq\lceil\tfrac{\omega(G)}{5}\rceil+1$. If $R\cap F=\emptyset$, then

which is a clear contradiction. Hence we may assume that $R$ is small with respect to $X$. We may also assume that $R\not\in\mathcal{F}$, since that case is clear. Suppose $R$ is a touching detour. Thus by Step 5, $\mathcal{F}$ contains two small touching detours $P,Q$ with different home components. Without loss of generality, suppose that the home component for $P$ is different to the home component for $R$. Since $P$ and $R$ are touching detours and need to intersect while having different home components, it follows they intersect in $X$ itself, and thus $R$ intersects $F$. Hence we may assume that $R$ is a crossing detour. The first subcase we will now consider is the case when $R$ is open and no touching detours exist. Thus by Step 4 and the existence of $R$ there exists a small open crossing detour $P\in\mathcal{F}$. We construct a separation $(M,X,N)$ where the detours $P$ and $R$ both have one endvertex in $M$ and one in $N$. Thus by Lemma 2 it follows $(P\cap X)\cap(R\cap X)\neq\emptyset$, and hence $R$ intersects $F$.

The next subcase is when $R$ is open and crossing but some touching detours exist. Then by Step 5 there exist two small touching detours $P,Q\in\mathcal{F}$ with different home components. Partition the components of $G-X$ into $M$ and $N$ such that the home component of $P$ is in $M$, the home component of $Q$ is in $N$ and both $M$ and $N$ contain one endvertex of $R$; since $R$ is open this partition is achievable. Let $R_{M}$ be the subpath of $R$ created by deleting $N$ and pasting the remaining subpaths of $R$ together using the edges of $X$. Define $R_{N}$ analogously, and without loss of generality we say $|R_{M}|>\tfrac{1}{2}|R|$. Let $Q^{\prime}$ be a subpath of $Q$ with one endvertex in $N$, one endvertex in $X$ such that $|Q^{\prime}|>\tfrac{1}{2}|Q|$. If $R_{M}$ and $Q^{\prime}$ do not intersect in $X$ then they can be concatinated to create a longer detour, if they do intersect in $X$ then so do $R$ and $Q$, and so $R$ intersects $F$. These subcases account for when $R$ is open and crossing.

Finally we need to account for when $R$ is closed and crossing. Since $R$ exists, Step 2 will add some detours to $\mathcal{F}$. First suppose that all of the small, closed crossing detours have the same home component, and let $P$ be the detour Step 2(b) added to $\mathcal{F}$. Now let $M$ be the home component of $P$ (and $R$), and let $N$ be all other components of $G-X$. Thus by Lemma 2 applied to the separation $(M,X,N)$ it follows that $P$ and $R$ intersect in $X$, and thus $R$ intersects $F$.

Hence we may assume there exists a pair of small closed crossing detours $P,Q$ in $\mathcal{F}$ with different home components. Suppose $P,Q$ do not intersect in $X$ (that is, Step 2(c) occurred). Clearly we may also assume that $R$ does not intersect either $P$ or $Q$ in $X$. Label the home components of $P,Q,R$ by $C_{P},C_{Q}$ and $C_{R}$ respectively, and note $C_{P}\neq C_{Q}$. If $C_{P}=C_{R}$, then let $M=C_{P}$ and $N=G-X-C_{P}$ and apply Lemma 2 to $(M,X,N)$, so that $P$ intersects $R$ in $X$. So we assume $C_{P}\neq C_{R}$ and similarly that $C_{Q}\neq C_{R}$, that is, that $C_{P},C_{Q},C_{R}$ are three distinct components. Let $M=C_{P}\cup C_{Q}$ and $N=G-X-(C_{P}\cup C_{Q})$. If both $P$ and $Q$ intersect $N$ then by Lemma 2 the paths $P$ and $Q$ must intersect in $X$, which they do not. Hence without loss of generality we suppose $P$ does not intersect $N$, that is, $P\subset C_{P}\cup C_{Q}\cup X$. Since $P$ is crossing it must intersect both $C_{P}$ and $C_{Q}$. By a similar argument one of $P$ and $R$ cannot intersect $G-X-(C_{P}\cup C_{R})$; since $P$ intersects $C_{Q}$ it must be that $R\subset C_{P}\cup C_{R}\cup X$ and that $R$ intersects $C_{P}$ and $C_{R}$. Again, by a similar argument one of $Q$ and $R$ cannot intersect $G-X-(C_{Q}\cup C_{R})$, and given previous results it must be $Q\subset C_{Q}\cup C_{R}\cup X$ and that $Q$ intersects $C_{Q}$ and $C_{R}$.

We will now argue in a similar fashion to Lemma 2 to construct a longer detour. Consider the subpaths of $P\cap(C_{P}\cup X)$. All of the end vertices of these subpaths are in $X$ itself except for two inside $C_{P}$, and since $P$ crosses $X$ there are at least two subpaths in $P\cap(C_{P}\cup X)$. Create $P^{\prime}$ by connecting the subpaths of $P\cap(C_{P}\cup X)$ using the edges of $X$; because $P\cap(C_{P}\cup X)$ has at least two subpaths it follows that $P^{\prime}$ will contain at least one edge of $X$. Similarly, consider the subpaths of $P\cap(C_{Q}\cup X)$ and connect them up using edges of $X$ to create a path $P^{\prime\prime}$. Note that $P^{\prime\prime}$ will have both end vertices in $X$.

Construct $Q^{\prime},Q^{\prime\prime},R^{\prime},R^{\prime\prime}$ in the same way (substituting different components as appropriate). Finally, construct the path $P^{*}$ from $P^{\prime}$ and $Q^{\prime\prime}$ by removing an edge $e$ of $P^{\prime}$ in $X$ and adding the edges from the two endvertices of $e$ to the endvertices of $Q^{\prime\prime}$. This will be a path since $P^{\prime}\subset C_{P}\cup X$ and $Q^{\prime\prime}\subset C_{R}\cup X$ and $P,Q$ do not intersect in $X$. Construct $Q^{*}$ from $Q^{\prime}$ and $R^{\prime\prime}$ and $R^{*}$ from $R^{\prime}$ and $P^{\prime\prime}$ in the same fashion. Every vertex of $P,Q,R$ is used at least once in $P^{*},Q^{*},R^{*}$, but the vertices of $P\cap X$ are used twice (in both $P^{*}$ and $R^{*}$). Hence $|P^{*}|+|Q^{*}|+|R^{*}|>|P|+|Q|+|R|$, but since $P,Q,R$ are detours, it follows at least one of $P^{*},Q^{*},R^{*}$ is longer than a detour, a contradiction. This accounts for the case when there exists a pair of small closed crossing detours with different home components that do not intersect in $X$.

The final subcase we must consider is when every pair of small closed crossing detours with different home components has an intersection between the detours in $X$. (That is, Step 2(d) occurred.) Let $P,Q$ denote the pair we added to $\mathcal{F}$. Now at least one of these detours has a different home component to $R$; without loss of generality we suppose it is $P$. Then $P$ and $R$ would have been a legitimate choice of detours to add to $\mathcal{F}$ instead of $P$ and $Q$. But we know that for each valid choice the detours intersect in $X$, that is, $R$ must intersect $P$ in $X$ and is therefore intersects $F$. This completes all possible cases. ∎