# Adding a Tail in Classes of Perfect Graphs
## 5 \(P_{4}\)-Sparse Graphs
### Adding a Tail to a Spider  
In this section, we consider adding a tail \(uw\) to a spider \(H=(S_{H},K_{H},R_{H})\) where \(u\in V(H)\). In the following two lemmas, we address the cases of a thin or a thick spider \(H\), respectively. Lemma 6: _Consider the addition of a tail \(uw\) to a thin spider \(H=(S_{H},K_{H},\)\(R_{H})\) where \(u\) is a vertex of \(H\). Then, for the number \(f\) of fill edges (excluding the tail \(uw\)) in a minimum \(P_{4}\)-sparse completion of the graph \(H+uw\), the following holds:_  
1. _if_ \(u\in S_{H},f=|K_{H}|-1\) _if_ \(R_{H}=\emptyset\) _and_ \(f=|K_{H}|\) _otherwise;_
2. _If_ \(u\in K_{H},f=|K_{H}|-1\)_;_
3. _If_ \(u\in R_{H}\)_, Then_ \(f=\min\left\{\left.|R_{H}\setminus N_{H}[u]\right|,\,|K_{H}|+f^{\prime}\right.\right\}\) _where_ \(f^{\prime}\) _is the number of fill edges (excluding_ \(uw\)_) in a minimum_ \(P_{4}\)_-sparse completion of the graph_ \(H[R_{H}]+uw\)_._  
Proof. : 1. Let \(v\in K_{H}\) be the neighbor of \(u\) in \(H\). Then, we can obtain a \(P_{4}\)-sparse graph as follows: if \(R_{H}=\emptyset\), we connect \(u\) to all vertices in \(K_{H}\setminus\left\{v\right\}\) (we obtain a thin spider with \(S=(S_{H}\setminus\left\{u\right\})\cup\left\{w\right\}\), \(K=(K_{H}\setminus\left\{v\right\})\cup\left\{u\right\}\) and \(R=\left\{v\right\}\); that is, the tail \(uw\) is a wing of a \(P_{4}\) of a thin spider); otherwise, we connect \(v\) to all vertices in \(\left\{w\right\}\cup(S_{H}\setminus\left\{u\right\})\), which makes \(v\) universal in \(V(H)\cup\left\{w\right\}\) and \(u,w\) form a separate connected component in \(G[V(G)\setminus\left\{v\right\}]\); the total number of fill edges (excluding the tail \(uw\)) is precisely \(|K_{H}|-1\) if \(R_{H}=\emptyset\) and \(K_{H}\) otherwise. Moreover, this is the minimum number of fill edges (excluding \(uw\)) needed. First, we note that for each pair \(k_{i},s_{i}\) where \(k_{i}\in K_{H}\setminus\left\{v\right\}\) and \(s_{i}\in S_{H}\setminus\left\{u\right\}\), the vertices \(v,u,w,k_{i},s_{i}\) define an \(F_{5}\) or an \(F_{3}\) depending on whether the vertices \(v,w\) are adjacent or not, which implies that at least \(|K_{H}|-1\) fill edges (excluding \(uw\)) are needed. Then, if there is a way of obtaining a \(P_{4}\)-sparse graph by adding fewer than the number of fill edges mentioned in Case 1 of the statement of the lemma, it has to be the case that (i) \(R_{H}\
eq\emptyset\), (ii) each pair \(k_{i},s_{i}\) where \(k_{i}\in K_{H}\setminus\left\{v\right\}\) and \(s_{i}\in S_{H}\setminus\left\{u\right\}\) is incident on exactly \(1\) fill edge and (iii) no more fill edges exist. Let \(r\in R_{H}\) and \(k\in K_{H}\setminus\left\{v\right\}\). Then, the vertices \(v,u,w,k,r\) induce a forbidden subgraph (an \(F_{5}\) if \(k\) is non-adjacent to both \(u,w\) or an \(F_{6}\) (\(F_{1}\), resp.) if \(k\) becomes adjacent to \(u\) (\(w\), resp.) by means of a fill edge); thus, at least \(K_{H}\) fill edges are needed in this case. 2. Let \(v\in S_{H}\) be the neighbor in \(H\) of \(u\in K_{H}\). Then, connecting \(u\) to all vertices in \(S_{H}\setminus\left\{v\right\}\) (which makes \(u\) universal in \(H\)) or connecting \(w\) to all vertices in \(K_{H}\setminus\left\{u\right\}\) yields a \(P_{4}\)-sparse graph. Moreover, this is the minimum number of fill edges (excluding the tail \(uw\)) that need to be added. Suppose, for contrast, that we obtain a \(P_{4}\)-sparse graph after having added fewer than \(|K_{H}|-1\) fill edges (excluding \(uw\)) to the thin spider \(H\). Then, there exists a pair of adjacent vertices \(s,k\) with \(s\in S_{H}\setminus\left\{v\right\}\) and \(k\in K_{H}\setminus\left\{u\right\}\) such that neither \(s\) nor \(k\) is incident on a fill edge. Then, the vertices \(u,v,w,s,k\) induce a forbidden subgraph \(F_{5}\) or \(F_{3}\) if \(w\) and \(v\) are adjacent or not, respectively, a contradiction. 3.