# Adding a Tail in Classes of Perfect Graphs
## 5 \(P_{4}\)-Sparse Graphs
### Adding a Tail to a Spider
Let \(s\in S_{H}\) be the non-neighbor of \(k\) in \(H\) and \(A=(S_{H}\setminus\{u,s\})\cup\{r_{1},r_{2}\}\); the set \(A\) contains \(3\) vertices which are common neighbors of \(v,k\). If at least one of these \(3\) vertices (say, \(p\)) is not incident on a fill edge to \(u,w\), then the vertices \(u,v,w,k,p\) induce an \(F_{5}\); otherwise, all \(3\) of these vertices are incident on a fill edge to \(u,w\) (then these are all the fill edges) and the vertices \(u,v,w,s,k\) induce an \(F_{2}\). On the other hand, if no such vertex \(k\) exists, then both vertices in \(K_{H}\setminus\{v\}\) are incident on a fill edge to \(w\), accounting for \(2\) of the \(3\) fill edges; then there exists a vertex \(s^{\prime}\in S_{H}\setminus\{u\}\) which is not incident on a fill edge to \(w\) and the vertices \(u,v,w,s^{\prime},k^{\prime}\) (where \(k^{\prime}\in K_{H}\) is the non-neighbor of \(s^{\prime}\)) induce an \(F_{5}\). * \(v\) is incident on \(1\) fill edge (to \(u\) or \(w\)): There are \(2\) more fill edges; hence, there exist \(2\) vertices in the set \((S_{H}\setminus\{u\})\cup\{r_{1},r_{2}\}\) that are not incident on a fill edge connecting them to \(u\) or \(w\) and let these vertices be \(p_{1},p_{2}\). Then, the vertices \(u,v,w,p_{1},p_{2}\) induce an \(F_{5}\) if \(p_{1},p_{2}\) are connected by a fill edge or an \(F_{3}\) otherwise. * \(v\) is incident on \(2\) fill edges connecting it to \(u\) and \(w\): Then, there is \(1\) more fill edge; hence, there exists a vertex \(k\in K_{H}\setminus\{v\}\) that is not incident on the fill edge. Moreover, there exist \(2\) vertices in the set \((S_{H}\setminus\{u,s\})\cup\{r_{1},r_{2}\}\) that are not incident on a fill edge connecting them to \(u\) or \(w\) (where \(s\in S_{H}\) is the non-neighbor of \(k\)); let these vertices be \(p_{1},p_{2}\). Then, the vertices \(u,w,k,p_{1},p_{2}\) induce an \(F_{5}\) if \(p_{1},p_{2}\) are adjacent or an \(F_{3}\) otherwise. 4. \(|K_{H}|\geq 4\) and \(R_{H}=\emptyset\): Suppose, for contrast, that there is a \(P_{4}\)-sparse completion of \(H+uw\) with at most \(|K_{H}|-1\) fill edges (excluding the tail \(uw\)). Again, we distinguish three cases depending on whether \(v\) is incident on \(0\), \(1\) or \(2\) fill edges: * \(v\) is not incident on a fill edge: If there exists a vertex \(s\in S_{H}\setminus\{u\}\) not incident on a fill edge to \(u\), \(w\) or to its non-neighbor \(k\in K_{H}\) in \(H\), the vertices \(u,v,w,s,k\) induce an \(F_{5}\) if \(k,w\) are connected by a fill edge or an \(F_{2}\) otherwise; if all vertices in \(S_{H}\setminus\{u\}\) are incident on a fill edge to \(u\), \(w\) or their non-neighbor in \(K_{H}\), then there are no more fill edges and the vertices \(u,v,w,k,k^{\prime}\) (for any \(k,k^{\prime}\in K_{H}\setminus\{v\}\) induce an \(F_{6}\)\(v\) is incident on 1 fill edge (to \(u\) or \(w\)): Then, the remaining fill edges are at most \(|K_{H}|-2\) in total. If there exist two vertices \(s_{1},s_{2}\in S_{H}\setminus\{u\}\) not incident on a fill edge to \(u\) or \(w\), the vertices \(u,v,w,s_{1},s_{2}\) induce an \(F_{5}\) or an \(F_{3}\) depending on whether \(s_{1},s_{2}\) are connected by a fill edge or not. Thus, there cannot be two such vertices \(s_{1},s_{2}\); this implies that the remaining fill edges are precisely \(|K_{H}|-2\) and they connect all but one vertex in \(S_{H}\setminus\{u\}\) to \(u\) or \(w\); let that vertex be \(s\). Then, the vertices \(u,v,w,s,k^{\prime}\) (where \(k^{\prime}\in K_{H}\setminus\{v\}\) is a neighbor of \(s\) in \(H\)) induce an \(F_{6}\) or an \(F_{1}\) if the fill edge incident on \(v\) connects it to \(u\) or \(w\), respectively. * \(v\) is incident on 2 fill edges connecting it to \(u\) and \(w\): Then, the remaining fill edges are at most \(|K_{H}|-3\) in total; hence, there exist two pairs of non-adjacent vertices \(s_{1},k_{1}\) and \(s_{2},k_{2}\) with \(s_{1},s_{2}\in S_{H}\setminus\{u\}\) and \(k_{1},k_{2}\in K_{H}\setminus\{v\}\) such that none of \(s_{1},s_{2},k_{1},k_{2}\) are incident on a fill edge to \(u\) or \(w\).