# Adding a Tail in Classes of Perfect Graphs
## 5 \(P_{4}\)-Sparse Graphs
### The Algorithm
So, suppose for contrast that the spider \(W\) has \(|S_{W}|=|K_{W}|\geq 3\) and let \(w,b,d\in S_{W}\) and \(u,a,c\in K_{W}\) with the corresponding \(S\)-\(K\) pairs being \(w\) and \(u\), \(b\) and \(a\) and \(d\) and \(c\). The spider \(W\) can be thin or thick. * The spider \(W\) is thin. Then, \(ab\in E(G)\); otherwise, the removal of \(ab\) would produce a \(P_{4}\)-sparse graph with fewer fill edges (\(b\) is isolated in \(G[V(W)]\)), a contradiction; similarly, \(cd\in E(G)\). Moreover, \(ac\in E(G)\): as above, if \(a,c\) do not belong to the same connected component of the induced subgraph \(G[V(W)]\), then adding the tail \(uw\) to the connected component of \(G[V(W)]\) to which \(u\) belongs would result in fewer fill edges (e.g., the fill edge \(ac\) will not be needed); if \(a,c\) belong to the same connected component of \(G[V(W)]\) but \(ac\
ot\in E(G)\), then there exists a chordless path \(\rho\) connecting them in the subgraph \(G[K_{W}\cup R_{W}]\) and the vertices in \(V(\rho)\cup\{b,d\}\) induce a \(P_{\ell}\) with \(\ell\geq 5\), in contradiction to the \(P_{4}\)-sparseness of \(G\). However, then, \(G\) contains the \(P_{4}\)_baks_ and \(ab\) belongs to a spider. * The spider \(W\) is thick. Then, \(w\in S_{W}\) is incident on the tail \(uw\) and \(|K_{W}|-2\geq 1\) fill edges. Since we can make \(u\) universal in \(G[V(W)\setminus\{w\}]\) by using a single fill edge and then use Formation 2, it is clear that building spider \(W\) does not result in fewer fill edges. Thus, \(G_{OPT}\) with a spider \(W\) with \(|K_{W}|\geq 3\) has no fewer fill edges than if we use Formation 2. Therefore, the \(P_{4}\)\(wuab\) belongs to a spider with clique size equal to \(2\), which thus is thin. Then, Property P1 in Lemma 4 implies that \(w\), \(u\) and \(a\) are adjacent to all theneighbors of \(b\) except for \(a\) in \(G_{OPT}\) and thus at least to the neighbors of \(b\) except for \(a\) in \(G\); thus, in \(G_{OPT}\),  
* Fill edges connect vertex \(w\) to the vertices in \(((V_{0}\cup\cdots\cup V_{k-1})\setminus\{a\})\cap N_{G}(b)=[(V_{0}\cup\cdots\cup V _{k-1})\setminus\{a\}]\cap N_{G}(u)\);
* Vertex \(u\) and \(w\) are adjacent to all neighbors of \(b\) in \(V_{k}\); that is, fill edges connect \(u\) to the vertices in \((V_{k}\cap N_{G}(b))\setminus N_{G}(u)\) and \(w\) to the vertices in \(V_{k}\cap N_{G}(b)\);
* Vertex \(a\) is adjacent to all the vertices in \((V_{j}\cap N_{G}(b))\) and thus fill edges connect \(a\) to all vertices in \((V_{j}\cap N_{G}(b))\setminus N_{G}[a]=(V_{j}\cap N_{G}(u))\setminus N_{G}[a]\). Additionally, Property P2 in Lemma 4 implies that because \(a\) is adjacent to all the vertices in \(V_{j+1}\cup\cdots\cup V_{h}\) and to the vertices in \(V_{j}\cap N_{G}(a)\) in \(G_{OPT}\) (because it is adjacent to them in \(G\)), then so must be vertex \(u\) in \(G_{OPT}\); thus, in \(G_{OPT}\), fill edges connect \(u\) to the vertices in \((V_{j+1}\cup\cdots\cup V_{h})\setminus N_{G}(u)\) and to the vertices in \((V_{j}\cap N_{G}(a))\setminus N_{G}(u)\) (the set \((V_{j}\cap N_{G}(a))\setminus N_{G}(u)\) is non-empty if and only if \(t_{j}\) is a 2-node). Now, let us consider using Formation 2 right below node \(t_{j}\) in the \(P_{4}\)-sparse tree \(T_{G}\) of \(G\); then, the number of fill edges is \(|(V_{j+1}\cup\cdots\cup V_{h})\setminus N_{G}(u)|+|(V_{0}\cup\cdots\cup V_{j} )\cap N_{G}(u)|\); the former term corresponds to fill edges incident on \(u\), the latter to fill edges incident on \(w\). Then, because \(j<k\) and \(|((V_{0}\cup\cdots\cup V_{k-1})\setminus\{a\})\cap N_{G}(u)|=|(V_{0}\cup\cdots \cup V_{k-1})\cap N_{G}(u)|-1\), the only possibility for \(G_{OPT}\) to use fewer fill edges than using Formation 2 after node \(t_{j}\) requires that  
1. \(k-1=j\implies k=j+1\);
2. \((V_{j}\cap N_{G}(u))\setminus N_{G}[a]=\emptyset\);
3. \(V_{k}\cap N_{G}(b)=\emptyset\) which implies that \(b\) is isolated in \(G[V_{k}]\) and also implies that \((V_{k}\cap N_{G}(b))\setminus N_{G}(u)=\emptyset\);
4.