Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion

The start of our results is a structure theorem for prison-free graphs. To begin with, note that the 4-vertex induced subgraphs of a prison are $K_4$, the diamond and the paw; see Figure 1. The structure of diamond-free and paw-free graphs are known: A graph is diamond-free if and only if it is strictly clique irreducible, i.e., every edge of the graph lies in a unique maximal clique [17], and a graph is paw-free if and only if every connected component is either triangle-free or complete multipartite [16]. The structure of prison-free graphs generalizes both.

A complete multipartite graph with classes $P_1,\mathrm{\dots },P_m$ is a graph whose vertex set is the disjoint union $P_1\cup \mathrm{\dots }\cup P_m$ and with an edge $uv$ for $u\in P_i$ and $v\in P_j$ if and only if $i\ne j$. Note that a clique is a complete multipartite graph where every part is a singleton. We show the following.

Furthermore, let $cm{d}_p(G)$ for $p\in \mathbb{N}$ be the collection of all inclusion-wise maximal $F\subseteq V(G)$ such that $G[F]$ is complete multipartite with at least $p$ classes. We show that $cm{d}_4(G)$ induces a form of partition of the cliques of $G$.

In particular, every $K_p$ in $G$, $p\ge 4$ is contained in a unique $F\in {\mathrm{cmd}}_4(G)$. It also follows that $cm{d}_4(G)$ can be enumerated in polynomial time in prison-free graphs.

We show that Prison-free Edge Completion is incompressible, i.e., admits no polynomial kernel parameterized by $k$ unless the polynomial hierarchy collapses. Counterintuitively, this result exploits the property that minimum solutions for the problem can be extremely expensive – we can design a sparse graph $G$ such that every prison-free supergraph of $G$ contains $\mathrm{\Theta }(n^2)$ edges (for example, by ensuring that the only possible $cm{d}_4$-decomposition of a prison-free supergraph of $G$ consists of a single component $F=V(G)$). More strongly, we use this to show an additive gap hardness version of the problem.

With this in place, we can proceed with the lower bound using standard methods, using the notion of cross-composition [1, 11]. We follow the method used in previous lower bounds against kernelization of $H$-free edge modification problems [14, 3]. Given a list $I_1,\mathrm{\dots },I_t$ of instances of the above gap-version of Prison-Free Edge Completion with parameter value $k$, our task is to produce an instance of Prison-Free Edge Completion with parameter ${(k^{\prime }+\log t)}^{O(1)}$ which corresponds to the OR of the instances $I_i$. For this, we define a binary tree of height $O(\log t)$ and place the instances at the leaves of the tree. At the root of the tree, we place a single induced prison. For the internal nodes, we design propagational gadgets with the function that if the gadget at the node is edited, then one of the gadgets at the children of the node must be edited as well. Finally, for every instance $I_j=(G_j,k)$ with an edge $e_j$ such that $G_j-e$ is prison-free, we connect $e_j$ to the corresponding gadget at the leaf of the tree and remove $e_j$ from $G_j$. This forces at least one edge $e_j$, $j\in [t]$ to be added to the resulting graph and the original instance $I_j=(G_j,k)$ must be solved.

The crux is that, unlike previous proofs (for example in Cai and Cai [3] when $H$ is 3-connected) we cannot “control” the spread of the edge completion solution to be confined to $G_j$. On the contrary, the solution must spread all the way to the root and incorporate all vertices from gadgets on the root-leaf path of the binary tree into a single complete multipartite component of the resulting graph $G^{\prime }$. Thus, we have no tight control over the number of edges added in the corresponding solution. However, by the strong lower bound on gap-hardness of Theorem 4 we do not need tight control – we can simply set the additive gap $g$ large enough that the number of edges added outside of $G_j$ in the resulting propagation is a lower-order term compared to $g$.

The kernelization algorithm depends directly on the structural characterization of prison-free graphs. We start by using the sunflower lemma to obtain a small set ${𝒫}^{\prime }$ of prisons in the graph $G$ such that any set of edges of size at most $k$ that intersects all prisons in ${𝒫}^{\prime }$ has to intersect all prisons in $G$. We let $S$ be the set of vertices of these prisons. Note that $|S|=𝒪(k^8)$, and outside of $S$ we only need to be concerned by prisons that are created by deleting some edge from $G$. This lets us delete all edges not in $E(G[S])$ that do not belong to a strict supergraph of a prison. In addition, if a prison in $G$ contains a single edge inside $S$, then such an edge has to be included in every solution of size at most $k$, so it can be deleted and $k$ decreased. After exhaustive application of these two reduction rules, we show that the edges of $G[V(G)\setminus S]$ can be partitioned into maximal complete multipartite subgraphs of $G[V(G)\setminus S]$ (even those which do not occur in $cm{d}_4(G[V(G)\setminus S])$). For each of these maximal complete multipartite subgraphs, we can check whether it is in some larger complete multipartite subgraph $F$ in $G$ that is nicely separated from the rest of $G$, in the sense that every $x\in V(G)\setminus F$ neighbors vertices in at most one class of $F$. For any such $F$, no supergraph of a prison can contain edge both outside and inside of $F$ and edges inside of $F$ can be safely deleted from $G$. This allows us to bound the number of maximal complete multipartite subgraphs outside of $S$ by $𝒪({|S|}^3)$. In addition, we show that any supergraph of a prison in $G$ that contains an edge fully outside of $S$ is fully contained in $S\cup F$ for a single maximal multipartite subgraph $F$ of $G[V(G)\setminus S]$. This allows us to treat these multipartite subgraphs separately. Moreover, using the fact that for any edge $e\in G[S]$, the graph $G[V(G)\setminus (S\setminus e)]$ is still prison-free, we can show that the interaction between $S$ and a maximal multipartite subgraph $F$ of $G[V(G)\setminus S]$ is very structured. This allows us to reduce the size of each of these subgraphs and we obtain the following theorem.

In Section 2 we derive the basic facts about prison-free graphs. Section 3 contains the lower bound against Prison-free Edge Completion and Section 4 contains the polynomial kernel for Prison-free Edge Deletion. We conclude in Section 5.

We can only give a brief sketch here and refer to the full version for details. The result is shown by a reduction from Vertex Cover on cubic graphs. At its heart is the following principle. We create a graph $G$ which has a single induced $K_4$. Then by Lemma 9, for any minimal prison-free completion set $A$ of $G$, $V(A)$ will be contained in a single complete multipartite component $F$ of $G\cup A$. Using forbidden edges, we can have tight control over the partition of $F$, which lets us predict $|A|$ well. In particular, we can ensure that the number of edges $|A|$ added scales quadratically with $|V(A)|$.

Our reduction uses two gadgets: cloning components, of sufficiently large length $\mathrm{\ell }$, and disjoint propagational components. Let $(G,t)$ where $G=(V,E)$ be an input instance of Vertex Cover where $G$ is a cubic graph. Using one initial cloning component $X_0$ with a single seeded active edge $e$, we can force the propagation of $e$ into $m=|E|$ disjoint activation edges $e_i$, one for every edge of $E$. For every edge $ab\in E$, associated with an edge $e_i$ of $X_0$, we create a disjoint propagational component with input edge $e_i$ and output edges $f_{a,i}$ and $f_{b,i}$ associated with the vertices $a$ and $b$ of $G$. Finally, for every vertex $v\in V$ we create a very large cloning component, which contains all edges $f_{v,j}$ associated with it, and whose length $\mathrm{\ell }$ depends on the desired gap $g$. Thus, prison-free completion sets $A$ of the resulting graph $G^{\prime }$ which activate the cloning components of $s$ distinct vertices of $G$, lead to a prison-free supergraph $G^{\prime }\cup A$ of $G^{\prime }$ where the unique complete multipartite component $F$ of $cm{d}_4(G^{\prime }\cup A)$ contains $O(\mathrm{\ell }s)$ vertices, guaranteeing that $|A|=\mathrm{\Theta }({(s\mathrm{\ell })}^2)$ for a corresponding minimum solution $A$. We can now achieve the desired gap by tuning $\mathrm{\ell }$ to be sufficiently large. $◀$

We show that the construction above is a cross-composition into Prison-free Edge Completion with parameter $k$. Consider briefly the two cases. First, if for some $i\in [t]$ the input instance $(G_i,k_0,g_0)$ is positive, let $A_i$ be a prison-free completion set for $G_i$ with $|A_i|\le k$. By Lemma 15 there is a prison-free completion set $A\supseteq A_i$ for $G$ that modifies edges along the root-leaf path to $L_i$ of the binary tree, and does not contain any other output edge of the tree. By Lemma 9 and minimality of $A$ and $A_i$ we may now assume that $A$ touches no vertices of the binary tree except on the root-leaf path to $L_i$, and contains no further edges inside $G_i$ beyond $A_i$. Let $n_t$ be the number of vertices in the gadgets of the tree incident with edges of $A$; since the tree has height $h=O(\log t)$ and each node is constant size, we have $n_t=O(\log t)$. Thus

On the other hand, assume that for every $i\in [t]$ the minimum prison-free completion set $A_i$ for $G_i$ has $|A_i|\ge k_0+g_0$. Let $A$ be a prison-free completion set for $G$. By Lemma 15 there is some $i\in [t]$ such that the activation edge $e_i$ of $G_i$ is contained in $A$. Thus $A$ contains a prison-free completion set for $G_i$ and $|A|\ge k_0+g_0$. By the construction of Theorem 4, we can tune the parameters so that these quantities separate, and choose a parameter $k$ where

in which case the reduction is complete. $◀$

The proof is a straightforward application of Lemma 16. Let $𝒮=\{E(P)\mid P\text{ is a prison in }G\}$. Note that each set $X\in {𝒮}_0$ contains precisely $8$ edges. We iteratively apply Lemma 16 on $𝒮$ to find a sunflower of size $k+2$. If the core of the sunflower ${𝒮}^{\prime }$ is empty, then $G$ contains $k+2$ edge-disjoint prisons and $(G,k)$ is no instance. Else any solution of size at most $k$ interesects the core and that is the case even if we require to hit only $k+1$ prisons of ${𝒮}^{\prime }$, so we remove arbitrary prison from $𝒮$ and repeat the procedure until no suflower of size $k+2$ can be find. At that point $𝒮$ contains at most $8!\cdot {(k+1)}^8$ many prisons and any $A\subseteq E(G)$ with $|A|\le k$ that intersect all of the prisons that are left in $𝒮$ intersects all prisons in $G$. We let $S$ to be the set of all vertices in these prisons. $◀$

For the rest of the section and of the proof, we let $S$ be the set computed by Lemma 17. It follows, as long as we keep $G[S]$ as the subgraph of the reduced instance, we only need to be concerned about the prisons that are created by removing some edge from $G$, as all the prisons that were in $G$ to start with are hit by a set $A$ of at most $A$ edges as long as $G[S]\mathrm{\Delta }A$ is prison-free. Given the above, the following two reduction rules are straightforward.

Thanks to these Reduction Rules, we found a set $S$ of vertices of size polynomial in $k$ such that for any subset $S^{\prime }$ of vertices of $S$ such that $G[S^{\prime }]$ has at most one edge, $G[\overline{S}\cup S^{\prime }]$ is prison-free. We note that we assume that all reduction rules are applied exhaustively; that is whenever a reduction rule is applicable, we apply it and restart the process from the beginning. Hence, in all statements in the rest of the section, we implicitely assume that none of the reduction rules can be applied.

Since $F$ has three classes, there are $u,v,w$ such that $uvw$ is a triangle in $G[\overline{S}]$. Due to Reduction Rule 1, each edge of $F$ is in a strict supergraph of a prison and hence in $K_4$ in $G$. Now given a $K_4$ $(a,b,u,v)$ that contains $uv$, we conclude that $w$ is adjacent to either $a$ or $b$, else $(a,b,u,v,w)$ induces a prison with at most one edge in $S$ and Reduction Rule 2 applies. Hence $\{u,v,w\}$ is a subset of a $K_4$, say $(u,v,w,s)$. As a consequence of Lemma 7 and since $G[\overline{S}]$ is prison-free, one can show that $F$ has to be fully included in the $K_4$-free part of $G[\overline{S}]$, and hence $s\in S$. Now, any vertex $x\in F\setminus \{u,v,w\}$ is adjacent to exactly two vertices in $\{u,v,w\}$ and hence if $sx\notin E(G)$, then $(u,v,w,s,x)$ induces a prison without an edge in $S$, which is impossible due to the construction of $S$. $◀$

The Lemma follows for $F\in cm{d}_4(G[\overline{S}])$ by Lemma 7. Hence, we can assume $F\in cm{d}_3(G[\overline{S}])\setminus cm{d}_4(G[\overline{S}])$. For the sake of contradiction, assume that for $x\in \overline{S}\setminus F$, we have that $N(x)\cap F$ contains an edge $uv$. Since $F$ has three classes, for every $w$ in the class $C$ that does not contain $u$ nor $v$, we have that $uvw$ is a triangle. Moreover, similarly as in the proof of Lemma 18, one can show using Lemma 7 that $(u,v,w,x)$ cannot be $K_4$ and so $wx\notin E(G)$. Since, $F$ is inclusion maximal, there is $a\in F\setminus C$ such that $xa\notin E(G)$. By Lemma 18, there is $s\in S$ with $F\subseteq N(s)$. But then either $(u,v,w,s,x)$ or $(u,v,a,s,x)$ induces a prison with no edge in $G[S]$ (depending on whether $sx\in E(G)$ or not), which is impossible due to the construction of $S$. $◀$

For the sake of contradiction, let $P$ be a supergraph of a prison of $G$ that has an edge $uv$ in $F\in cm{d}_3(G[\overline{S}])$ and there is $x\in P\setminus (S\cup F)$. One can show that due to Lemma 19 and application of Reduction Rule 2, $P=(a,b,u,v,x)$ is a strict supergraph of a prison with $\{a,b\}\subseteq S$ and $vx$ (or $ux$) being the only non-edge of $P$. Moreover, $F$ contains triangle $uvw$, as it has at least three classes and $wx\notin E(G)$ by Lemma 19. Due to Reduction Rule 2, $(u,v,w,a,b)$ cannot induce a prison, and either $wa\in E(G)$ or $wb\in E(G)$. If $wa\in E(G)$ (resp. $wb\in E(G)$), then $(x,a,u,w,v)$ (resp. $(x,b,u,w,v)$) induces a prison in $G$ with at most one edge in $G[S]$, contradicting application of Reduction Rule 2. $◀$

Let’s now focus on the edges of $\overline{S}$ that are not in any triangle. We show that since Reduction Rules 1 and 2 has been exhaustively applied, even these edges can be partitioned to maximal complete bipartite subgraphs.

Let $B$ be the set of edges of $G[\overline{S}]$ that are not in any triangle in $G[\overline{S}]$. For all $e=ab\in E(G[S])$, we note $B_e=B\cap \{uv:u,v\in N(a)\cap N(b)\}$. Note that every edge $f\in B$ belongs to a $K_4$ in $G$ due to the application of Reduction Rule 1. Since, $f$ is not in any triangle in $G[\overline{S}]$, it follows that it is in some $B_e$ for $e\in E(G[S])$. On the other hand, we show that if $B_{e_1}\cap B_{e_2}\ne \mathrm{\varnothing }$, then $B_{e_1}=B_{e_2}$, otherwise $G$ contains a prison with at most one edge in $G[S]$, which gives us the following lemma.

The following lemma is a straightforward consequence of Reduction Rule 2, since for every $e\in E(S)$, $G[\overline{S}\cup e]$ is prison-free and hence $N_G(e)\cap \overline{S}$ is $\overline{P_3}$-free.

Assume that there is an induced supergraphs of a prison $P=(a,b,u,v,w)$, where $uv$ in $B_e$ and $w\in \overline{S}\setminus B_e$. It follows from Reduction Rule 2 and the fact that $uv$ is not in a triangle in $G[\overline{S}]$ that (1) $P$ is a strict supergraph of a prison with only non-edge $uw$ (resp. $vw$) and (2) $\{a,b\}\subseteq S$. By Lemma 21, $B_e=B_{ab}$. Since $B_e$ is maximal complete bipartite subgraph of $G[\overline{S}]$, the class that contains $v$ (resp. $u$), contains a vertex $v^{\prime }$ (resp. $u^{\prime }$) with $v^{\prime }w\notin E(G)$. But then $(a,b,v,v^{\prime },w)$ (resp. $(a,b,u,u^{\prime },w)$) induces a prison in $G$ with only one edge inside $S$, which is a contradiction. $◀$

It follows that we can partition the edges of $G[\overline{S}]$ in complete multipartite subgraphs, where one of these complete multipartite subgraphs can intersect another in at most one class. The following reduction rule lets us reduce the number of complete multipartite subgraphs in this partition to ${|S|}^3+{|S|}^2=𝒪(k^{24})$. Given this bound, we will reduce size of each of these components as well as number of isolated vertices in $G[\overline{S}]$ by a polynomial function in $k$ as well.

It is not difficult to show that there is no supergraph of a prison in $G$ that contains an edge with both endpoints in $F$ and at the same time an edge with at least one endpoint outside of $F$. Given this for every $A\subseteq E(G)$, every prison in $G\mathrm{\Delta }A$ is either all edge in $F$ or all edges in $G-E(F)$, since $F$ is complete multipartite and hence prison-free, it suffices to hit all prisons in $G-E(F)$. $◀$

Recall that we always assume that none of the previous reduction rules can be applied, in particular from now on we assume also that Reduction Rule 3 is not applicable.

From now on, we denote $ℱ=cm{d}_3(G[\overline{S}])\cup \{B_e\mid e\in E(G[S])\}.$

Clearly every edge in $G[\overline{S}]$ is in a maximal complete multipartite subgraph of $G[\overline{S}]$. We only need to show that each edge is in precisely one such subgraph and that their number is at most ${|S|}^3+{|S|}^2$. First note the edges in $B$ are partitioned into at most $|E(G[S])|\le {|S|}^2$ many complete bipartite graphs by Lemma 21. Hence, we only need to consider the edges that are in some $F\in cm{d}_3(G[\overline{S}])$. It is a rather straightforward consequence of Lemma 19 that any edge $e$ in $F$ cannot be in any other maximal complete multipartite subgraph in $cm{d}_3(G[\overline{S}])$. It remains to show that show that $|cm{d}_3(G[\overline{S}])|\le {|S|}^3$.

We will now define a function $f:cm{d}_3(G[\overline{S}])\to cm{d}_4(G)$ such that for all $F\in cm{d}_3(G[\overline{S}])$, it holds that (1) $F\subseteq f(F)$ and (2) $f(F)$ contains at least one vertex in $S$. That is $f$ is injective. We will show that every edge in $G[S]$ is in at most $|S|$ many complete multipartite subgraph in the image of $f$ and every element of the image of $f$ contains an edge of $G[S]$, bounding $cm{d}_3(G[\overline{S}])$ by $|E(G[S])|\le {|S|}^3$.

If $F\in cm{d}_4(G[\overline{S}])$, then since Reduction Rule 3 has been exhaustively applied, there is $v\in S$ such that $N(v)$ intersects at least two classes of $G[F]$, and since $G[\overline{S}\cup \{v\}]$ is prison-free and $F$ contains a $K_4$, $G[F\cup \{v\}]$ is complete multipartite. We define $f(F)$ as any maximal complete multipartite component of $G$ containing $F\cup \{v\}$. Else, if $F\in cm{d}_3(G[\overline{S}])-cm{d}_4(G[\overline{S}])$, then by Lemma 18, there is a vertex $s\in S$ such $F\subseteq N(s)$ and $G[F\cup \{s\}]$ is a complete multipartite graphs with at least four parts. We define $f(F)$ as a maximal complete multipartite subgraph of $G$ containing $F\cup \{s\}$.

There are thus at most ${|S|}^3$ elements of $Im(f)$ that contains an edge in $S$.

So $|Im(f)|\le {|S|}^3$. Since $f$ is injective, $|cm{d}_3(G[\overline{S}])|\le {|S|}^3$. Therefore, $|ℱ|=|cm{d}_3(G[\overline{S}])|+|\{B_e\mid e\in E(G[S])\}|\le {|S|}^3+{|S|}^2$. $◀$

We will have a kernel once we have bounded the size of a maximal complete multipartite subgraphs and the number of isolated vertices in $G[\overline{S}]$. Before we show how to bound those, let us observe the following two simple lemmas.

The bound on the size of $G^{\prime }$ follows from the fact that that $|S|=𝒪(k^8)$, $|ℱ|\le {|S|}^3+{|S|}^2$, and Lemma 29. Now, $G^{\prime }$ is an induced subgraph of $G$ and hence for every $A\subseteq E(G)$, if $G\mathrm{\Delta }A$ is prison-free, then also $G^{\prime }\mathrm{\Delta }(A\cap E(G^{\prime }))$ is. Therefore, if $(G,k)$ is yes-instance, then so is $(G^{\prime },k)$.

For the rest of the proof, let us assume that $(G^{\prime },k)$ is yes-instance and let $A\subseteq E(G^{\prime })$ be such that $|A|\le k$ and $G^{\prime }\mathrm{\Delta }A$ is prison-free. We show that $G\mathrm{\Delta }A$ is also prison-free. For the sake of contradiction, let’s assume that $P=(a,b,c,d,e)$ induces a prison in $G\mathrm{\Delta }A$. Let us distinguish two cases depending on whether $P$ contains an edge between two vertices outside of $S$ or not.

Case 1.

All edges of $P$ have at least one endpoint in $S$. Note that in this case, there are at most two vertices of $P$ outside of $S$.

If only one vertex of $P$, say $a$, is outside of $S$, then clearly $a$ is the only vertex of $P$ not in $G^{\prime }$. Note that this also means that none of the edges incident with $a$ is in $A$. Moreover, $G^{\prime }$ contains at least $2k+5$ vertices with the same neighborhood pattern in $\{b,c,d,e\}$, else $a$ would have been either in $M_{\mathrm{\varnothing }}$ or in $M_F$ for some $F\in ℱ$. Since $|A|\le k$, it follows that at least one of these $2k+5$ vertices, let’s call it $a^{\prime }$, is not incident to an edge in $A$ and in particular to an edge between $a^{\prime }$ and a vertex in $\{b,c,d,e\}$. However, then $(G^{\prime }\mathrm{\Delta }A)[\{a^{\prime },b,c,d,e\}]$ is isomorphic to $P$ and induces a prison, which is a contradiction with $G^{\prime }\mathrm{\Delta }A$ being prison-free.

Now assume that two vertices $a$ and $b$ are outside of $S$, and there is no edge between $a$ and $b$ in $G\mathrm{\Delta }A$. Note that the other non-edge of $P$ share an endpoint with $ab$, and w.l.o.g., we can assume it is $ac$. As at least one of $a$ and $b$ is not in $G^{\prime }$, $ab\notin E(G)$. Moreover, $ac\in E(G)\cap A$, else $P$ is a prison in $G$ and Lemma 17 implies that $A$ intersects $P$. Hence, $b\notin V(G^{\prime })$, by our marking procedure, there are at least $2k+5$ vertices $b^{\prime }$ in $V(G^{\prime })\setminus S$ with $\{c,d,e\}\subseteq N(b^{\prime })$ and $b{b}^{\prime }\notin E(G)$. One of these vertices is not incident on any edge in $A$. For such a vertex $b^{\prime }$, either $(a,b^{\prime },c,d,e)$ or $(a,b,b^{\prime },d,e)$ is a prison in $G^{\prime }\mathrm{\Delta }A$ depending on whether $a{b}^{\prime }\in E(G)$ or $a{b}^{\prime }\notin E(G)$.

Case 2.

$P$ contains an edge in $G-S$. Then by Lemmas 20 and 23, it follows that there exists $F\in ℱ$ such that $P\subseteq S\cup F$. Let $S^{\prime }=P\cap S$. Now, for $x\in P\setminus S$, If $x$ belongs to $C\in {𝒯}_F^1$, then by construction of $M_F$ and the fact that $|A|\le k$, $M_F$ either contains $x$ or a vertex $x^{\prime }$ such that (1) $x^{\prime }\in C$, (2) $N(x)\cap S^{\prime }=N(x)\cap S^{\prime }$, and (3) $x^{\prime }$ is not incident to any edge of $A$. On the other hand, if some of the vertices in $P\cap F$ are in the classes in ${𝒯}_F^2$, then all such vertices have exactly same neighborhood in $S$, moreover, either all their respective classes contain vertices in $M_F$, or there are at least five classes of $F$ that each has $2k+5$ vertices in $G^{\prime }$ and no vertex in these classes is incident on an edge in $A$. Hence, for each vertex $x$ in $P\cap F$ that belongs to a class $C\in {𝒯}_F^2$, we can find $C^{\prime }\in {𝒯}_F^2$ and $x^{\prime }\in C^{\prime }$ such that (1) $x^{\prime }\in M_F$, (2) $x^{\prime }$ is not incident on any edge in $A$, and (3) if $x$ and $y$ are in $P\cap F$, then $x^{\prime }$ and $y^{\prime }$ are in the same class of $F$ if and only $x$ and $y$ are. Let $P^{\prime }=(a^{\prime },b^{\prime },c^{\prime },d^{\prime },e^{\prime })$ be a subgraph of $G^{\prime }$ such that for all $x\in \{a,b,c,d,e\}$, if $x\in G^{\prime }$, then $x^{\prime }=x$ and else $x^{\prime }$ is computed as described above, depending on whether $x\in {𝒯}_F^1$ or $x\in {𝒯}_F^2$. It follows that for all $x,y\in \{a,b,c,d,e\}$, there is an edge $xy\in E(G)$ if and only if $x^{\prime }{y}^{\prime }\in E(G^{\prime })$. Moreover, since $xy\in A$ implies that $\{x,y\}\subseteq V(G^{\prime })$, it follows that $xy\in A$ if and only if $x^{\prime }{y}^{\prime }\in A$. Therefore, $P^{\prime }$ induces a prison in $G^{\prime }$, which is a contradiction.