# Adding a Tail in Classes of Perfect Graphs
## 5 \(P_{4}\)-Sparse Graphs
### The Algorithm  
Recall that \(t_{0}t_{1}\cdots t_{h}u\) is the path in the \(P_{4}\)-sparse tree \(T_{G}\) of \(G\) from the root \(t_{0}\) to the leaf for \(u\) and \(V_{i}\) (\(0\leq i<h\)) is the set of vertices associated with the leaves of the subtrees rooted at the children of \(t_{i}\) except for \(t_{i+1}\) and \(V_{h}\) is the set of vertices associated with the leaves of the subtrees rooted at the children of \(t_{h}\) except for the leaf corresponding to \(u\) (see Figure 5). Next we prove the conditions under which a minimum \(P_{4}\)-sparse completion of the graph \(G+uw\) uses fewer fill edges than when using Formation 1 or 2. **Lemma 8**. : _There exists a minimum \(P_{4}\)-sparse completion \(G_{OPT}\) of the graph \(G+uw\) which uses fewer fill edges than when using Formation 1 or 2 if and only if \(uw\) is a wing of a \(P_{4}\) in \(G_{OPT}\) which implies that_  
1. _[label=()]_
2. _either_ \(u\) _is a vertex of a spider in_ \(G\) _(Lemmas_ 6 _and_ 7 _apply_)_
3. _or there exists_ \(j\) _(_\(0\leq j<h\)_) such that_ \(t_{j}\) _is a_ \(1\)_-node,_ \(t_{j+1}\) _is a_ \(0\)_-node and there exist vertices_ \(a,b\) _such that_ \(a\in V_{j}\) _is universal in_ \(G[V_{j}]\) _and_ \(b\in V_{j+1}\) _is isolated in_ \(G[V_{j+1}]\)_._ _Then, in_ \(G_{OPT}\)_, the vertices_ \(u,w,a,b\) _induce a_ \(P_{4}\) _in a spider_ \((S,K,R)\) _with_ \(S=\{w,b\}\)_,_ \(K=\{u,a\}\) _and_ \(R=(V_{j+1}\setminus\{b\})\cup V_{j+2}\cup\cdots\cup V_{h}\)_._  
Proof. : If Formation 1 or Formation 2 cannot be used then Lemma 5 implies that \(uw\) is the wing of a \(P_{4}\) in \(G_{OPT}\). If \(u\) is a vertex of a spider in \(G\), then Lemmas 6 and 7 apply. So, below, assume that \(u\) is not a vertex of a spider in \(G\). For the tail \(uw\) to be the wing of a \(P_{4}\) in \(G_{OPT}\), we can show that there exist vertices \(x,y\) such that \(uxy\) is a \(P_{3}\) in the graph \(G\): if \(u,x,y\) do not all belong to the same connected component of \(G\), then we could add the tail \(uw\) to the connected component of \(G\) to which \(u\) belongs; thus, all the fill edges in \(G_{OPT}\) incident on vertices in different connected components (among which is at least one of \(ux\) and \(uy\)) will not be needed, a contradiction; if \(u,x,y\) belong to the same connected component of \(G\) but do not form a \(P_{3}\), then because \(u,y\) are not adjacent in \(G_{OPT}\) and thus neither are in \(G\), \(u,y\) are at distance \(2\) in \(G\) and there exists a \(P_{3}\)\(uay\) in \(G\) (note that \(u,y\) cannot be at distance \(\geq 4\) in \(G\) since then \(G\) would contain an induced \(P_{5}=F_{2}\) and they cannot be at distance \(3\) either since then there exists a \(P_{4}\)\(uaby\) in \(G\) and \(u\) would be a vertex of a spider in \(G\)). Therefore, in the following, consider that the minimum \(P_{4}\)-sparse completion \(G_{OPT}\) of \(G+uw\) contains an induced \(P_{4}\)\(wuab\) such that the graph \(G\) contains the induced \(P_{3}\)\(uab\); suppose that \(a\in V_{j}\) and \(b\in V_{k}\). Then, since \(u,b\) are not adjacent in \(G_{OPT}\), they are not adjacent in \(G\) either and thus their least common ancestor \(t_{k}\) in the \(P_{4}\)-sparse tree \(T_{G}\) of \(G\) is a \(0\)-node; it cannot be a \(2\)-node since then \(u\) would be a vertex of a spider. Moreover, \(a\) is a common neighbor of both \(u,b\) and thus the least common ancestor \(t_{j}\) of \(a,u\) in \(T_{G}\) is a \(1\)- or a \(2\)-node (in the latter case, \(a\) is a vertex of the clique of the spider) and \(j<k\). Let us now try forming the \(P_{4}\)\(wuab\), which clearly will belong to a spider, say \(W=(S_{W},K_{W},R_{W})\). We show that \(|S_{W}|=|K_{W}|=2\). First, note that the edge \(ab\) cannot belong to a spider in \(G\), since then \(u\) would belong to that spider as well (note that the vertices of \(G\) not belonging to a spider are either adjacent to all vertices of the spider or to none of them).