# Adding a Tail in Classes of Perfect Graphs
## 5 \(P_{4}\)-Sparse Graphs
### Adding a Tail to a Spider
If \(|R_{H}|\leq 1\), we obtain a \(P_{4}\)-sparse graph after having made \(u\) universal by connecting it to the remaining vertices in \(S_{H}\) by using \(|K_{H}|-1\) fill edges and adding the fill edge \(uv\) and those connecting \(u\) to the vertices in \(R_{H}\) if \(R_{H}\) is non-empty, for a total of \(|K_{H}|+|R_{H}|\) fill edges (excluding \(uw\)). If \(|R_{H}|\geq 1\), a \(P_{4}\)-sparse graph is obtained after having made \(v\) universal (by adding the fill edges \(vu\) and \(vw\)) and after having connected \(w\) to all vertices in \(K_{H}\setminus\{v\}\) (then the vertices in \((V(H)\setminus\{v\})\cup\{w\}\) induce a thick spider with \(K=K_{H}\setminus\{v\}\), \(S=S_{H}\setminus\{u\}\) and \(R=R_{H}\cup\{u,w\}\)) for a total of \(|K_{H}|+1\) fill edges (excluding \(uw\)). Below we show the minimality of this solution. Recall that \(v\in K_{H}\) is the non-neighbor of \(u\) in \(H\). We consider each of the five cases. (i) \(|K_{H}|=3\) and \(R_{H}=\emptyset\): Suppose, for contrast, that there is a \(P_{4}\)-sparse completion of \(H+uw\) with at most \(|K_{H}|-2=1\) fill edge (excluding \(uw\)). If \(v\) is incident on the unique fill edge (which connects \(v\) to \(u\) or \(w\)), then the vertices in \(S\cup\{v,w\}\) induce an \(F_{3}\). Now suppose that the fill edge is not incident on \(v\). Moreover, there exists at least one vertex \(s\in S_{H}\setminus\{u\}\) that is not incident on the fill edge either. Then, the vertices \(u,v,w,s,k\) (where \(k\in K_{H}\) is the non-neighbor of \(s\) in \(H\)) induce an \(F_{5}\) if \(k,w\) are connected by the fill edge or an \(F_{2}\) otherwise. 2. \(|K_{H}|=3\) and \(|R_{H}|=1\): Let \(R_{H}=\{r\}\). Suppose, for contrast, that there is a \(P_{4}\)-sparse completion of \(H+uw\) with at most \(|K_{H}|-1=2\) fill edges (excluding \(uw\)). 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 pair \(s,k\) of non-neighbors with \(s\in S_{H}\setminus\{u\}\) and \(k\in K_{H}\setminus\{v\}\) such that none of \(s,k\) is incident on a fill edge to \(u\) or \(w\), the vertices \(u,v,w,s,k\) induce an \(F_{2}\). Otherwise, since the number of such pairs is \(2\), for each such pair \(s,k\), exactly one of \(s,k\) is incident on a fill edge to \(u\) or \(w\) and no other fill edges exist. If there exists a vertex \(k\in K_{H}\setminus\{v\}\) not incident on a fill edge to \(w\), the vertices \(u,v,w,k,r\) induce an \(F_{5}\); otherwise, each of the fill edges connects each of the vertices in \(K_{H}\setminus\{v\}\) to \(w\) and then \(u,v,w,s,k\) (for any pair \(s,k\) of non-neighbors with \(s\in S_{H}\setminus\{u\}\) and \(k\in K_{H}\setminus\{v\}\)) induce an \(F_{5}\). * \(v\) is incident on \(1\) fill edge (to \(u\) or \(w\)): Then, there is \(1\) more fill edge; hence, there exist \(2\) vertices in the set \((S_{H}\setminus\{u\})\cup\{r\}\) 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 no other fill edge. Then, the vertices \(u,w,k,k^{\prime},r\) (where \(\{k,k^{\prime}\}=K_{H}\setminus\{v\}\)) induce an \(F_{6}\). 3. \(|K_{H}|=3\) and \(|R_{H}|\geq 2\): Let \(r_{1},r_{2}\) be two vertices in \(R_{H}\). Suppose, for contrast, that there is a \(P_{4}\)-sparse completion of \(H+uw\) with at most \(|K_{H}|=3\) fill edges (excluding \(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: Consider the case that there exists a vertex \(k\in K_{H}\setminus\{v\}\) that is not incident on a fill edge to \(w\).