# Adding a Tail in Classes of Perfect Graphs
## 5 \(P_{4}\)-Sparse Graphs
### Adding a Tail to a Spider
Then, we obtain a \(P_{4}\)-sparse graph by connecting \(u\) to \(v\); thus, \(u\) becomes universal in \(V(H)\cup\{w\}\). This is the minimum number of fill edges (excluding the tail \(uw\)) that need to be added since for any pair of non-neighbors \(s,k\) with \(s\in S_{H}\setminus\{v\}\) and \(k\in K_{H}\setminus\{u\}\), the vertices \(u,v,w,s,k\) induce a forbidden subgraph \(F_{3}\), a contradiction. 3. By connecting \(w\) to all vertices in \(K_{H}\) and then computing a minimum \(P_{4}\)-sparse completion of \(H[R_{H}\cup\{w\}]\), we obtain a \(P_{4}\)-sparse graph and the number of fill edges needed is \(|K_{H}|+f^{\prime}\). To prove the minimality of this number of fill edges, suppose, for contrast, that we can obtain a \(P_{4}\)-sparse graph from \(H+uw\) after having added at most \(|K_{H}|-1\) fill edges incident on vertices in \(S_{H}\cup K_{H}\) (excluding the tail \(uw\)). Then, there exists a pair \(s_{1},k_{1}\) of non-neighbors in \(H\) with \(s_{1}\in S_{H}\) and \(k_{1}\in K_{H}\), none of which is incident on a fill edge to \(u\) or \(w\). We distinguish the following two cases that cover all possibilities. * Each of the vertices in \(K_{H}\setminus\{k_{1}\}\) is incident on a fill edge to \(w\). These are precisely all the \(|K_{H}|-1\) fill edges; hence none of the vertices in \(S_{H}\setminus\{s_{1}\}\) is incident on a fill edge. Then, the vertices \(u,w,k_{1},s_{2},s_{3}\) (for any \(s_{2},s_{3}\in S_{H}\setminus\{s_{1}\}\)) induce an \(F_{3}\). * There exists at least one vertex in \(K_{H}\setminus\{k_{1}\}\) that is not incident on a fill edge to \(w\). Let that vertex be \(k_{2}\). Then, if there exists another vertex \(k_{3}\in K_{H}\setminus\{k_{1},k_{2}\}\) that is not incident on a fill edge to \(w\) as well, the vertices \(u,w,k_{2},k_{3},s_{1}\) induce an \(F_{6}\). On the other hand, if each of the vertices in \(K_{H}\setminus\{k_{1},k_{2}\}\) is incident on a fill edge to \(w\) (which implies that \(k_{3}\) is adjacent to \(w\)), then these fill edges are \(|K_{H}|-2\) in total, with only \(1\) remaining. If the non-neighbor \(s_{3}\) of \(k_{3}\) in \(S_{H}\) is not incident on a fill edge to \(u\) or \(w\), then the vertices \(u,w,k_{1},k_{2},s_{3}\) induce an \(F_{6}\), whereas if it is adjacent to \(u\) or \(w\), then there are no more fill edges. In particular, if \(s_{3}\) is adjacent to \(u\), the vertices \(u,k_{1},k_{3},s_{1},s_{3}\) induce an \(F_{6}\) and if it is adjacent to \(w\), the vertices \(u,w,k_{2},s_{1},s_{3}\) induce an \(F_{4}\). In each case, we get a contradiction. Thus every minimum \(P_{4}\)-sparse completion of \(H+uw\) requires at least \(|K_{H}|\) fill edges incident on vertices of \(S_{H}\cup K_{H}\). Now, if there exists a minimum \(P_{4}\)-sparse completion \(H^{\prime}\) of \(H+uw\) having fewer than \(|K_{H}|+f^{\prime}\) fill edges, then the fact that at least \(|K_{H}|\) of them are incident on vertices in \(S_{H}\cup K_{H}\) implies that \(H^{\prime}[R_{H}\cup\{w\}]\) is \(P_{4}\)-sparse using fewer than \(f^{\prime}\) fill edges in contradiction to the minimality of \(f^{\prime}\). If the (thin or thick) spider \(H\) belongs to a more general \(P_{4}\)-sparse graph, then Lemmas 6 and 7 imply the following result. Corollary 1: _Let \(u\) be a vertex of a \(P_{4}\)-sparse graph to which we add the tail \(uw\). Let \(t_{0}\cdots t_{h}u\) be the path in the \(P_{4}\)-sparse tree of \(G\) from the the root \(t_{0}\) to the leaf for \(u\) and let \(V_{0},\ldots,V_{h}\) be the corresponding vertex sets as mentioned before.