# Adding a Tail in Classes of Perfect Graphs
## 5 \(P_{4}\)-Sparse Graphs
Then, there exists a minimum \(P_{4}\)-sparse completion \(G^{\prime}\) of the graph \(G+uw\) such that for the \(P_{4}\)-sparse tree \(T_{G^{\prime}}\) of \(G^{\prime}\), one of the following three cases holds:_  
* _The nodes_ \(u,w\) _in_ \(T_{G^{\prime}}\) _have the same parent node which is a_ \(2\)_-node corresponding to a thin spider_ \((S,K,R)\) _with_ \(u\in K\) _and_ \(w\in S\)  
Figure 4: (left) A thin spider; (right) a thick spider. 2. _The_ \(P_{4}\)_-sparse tree_ \(T_{G^{\prime}}\) _results from_ \(T_{G}\) _by replacing the leaf for_ \(u\) _by the_ \(3\)_-treenode Formation_ 1 _shown in Figure_ 6_(left)._
3. _The_ \(P_{4}\)_-sparse tree_ \(T_{G^{\prime}}\) _results from_ \(T_{G}\) _by removing the leaf for_ \(u\) _and replacing a_ \(1\)_- or a_ \(2\)_-node_ \(t\) _in the path from the root of_ \(T_{G}\) _to the leaf for_ \(u\) _by the_ \(5\)_-treenode Formation_ 2 _in Figure_ 6_(right)._  
Proof. : Let \(G_{OPT}\) be a minimum \(P_{4}\)-sparse completion of the graph \(G+uw\) and let \(T_{OPT}\) be its \(P_{4}\)-sparse tree. We consider the following cases:  
1. _The leaves associated with \(u,w\) in \(T_{OPT}\) do not have the same parent node_: Let \(T_{R}\) be the \(P_{4}\)-sparse tree obtained from \(T_{OPT}\) by using Formation 2 just above the least common ancestor \(t\) of \(w\) and \(u\) in \(T_{OPT}\) (Figure 7); let \(G_{R}\) be the \(P_{4}\)-sparse graph corresponding to the tree \(T_{R}\). Then, \(G_{R}\) uses no more fill edges than \(T_{OPT}\). To see this, let \(t^{\prime}\) be the child of \(t\) that is an ancestor of the leaf for \(u\) (note that \(t^{\prime}\) may coincide with the leaf for \(u\)). Since \(u,w\) are adjacent in \(G_{OPT}\), \(t\) is a \(1\)- or a \(2\)-node. In either case, \(w\) is adjacent to all vertices in \((Z\cup\{u\})\setminus X\) corresponding to the leaves of the subtree of \(T_{OPT}\) rooted at \(t^{\prime}\) and all these edges, except for the tail \(uw\), are fill edges. If \(t\) is a \(1\)-node, then \(u\) is adjacent to all vertices in \(X\) (Figure 7) and thus \(G_{R}\) uses no more fill edges than \(G_{OPT}\). If \(t\) is a \(2\)-node, then \(u\) is adjacent to all the vertices in the clique \(K_{X}\) of the corresponding spider (which includes \(w\)). Moreover, because \(w\in K_{X}\), \(w\) is adjacent to all the vertices in \(K_{X}\setminus\{w\}\) and to at least one vertex in the independent set for a total of \(|K_{X}|\) fill edges; these fill edges can be used to connect \(u\) to the vertices in the independent set of the spider and thus \(G_{R}\) uses no more fill edges in this case too. Therefore, the graph \(G_{R}\) is a minimum \(P_{4}\)-sparse completion of \(G+uw\). Recall that in the \(P_{4}\)-sparse tree \(T_{G}\) of \(G\), the path from the root \(t_{0}\) to \(u\) is \(t_{0}t_{1}\cdots t_{h}u\) and \(V_{i}\) (\(0\leq i\leq 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}\) (where \(t_{h+1}\) is the leaf associated with \(u\)); see Figure 5.  
Figure 5: The path \(t_{0}t_{1}\cdots t_{h}u\) from the root \(t_{0}\) of the \(P_{4}\)-sparse tree to the leaf associated with \(u\) and the vertex sets \(V_{0},V_{1},\ldots,V_{h}\). Figure 6: **(left)** Formation 1; **(right)** Formation 2 where \(t\) is a \(1\)- or a \(2\)-node. Formation 1 is a special case of Formation 2 when \(Z=\emptyset\). We first observe that the induced subgraph \(G_{R}[Z]\) induced by the set of vertices \(Z\) corresponding to the leaves of the subtree of \(T_{R}\) rooted at node \(t\) coincides with the induced subgraph \(G[Z]\) (otherwise, \(G_{OPT}\) would include fill edges that could be removed in contradiction to its optimality); then, let \(t=t_{k}\). It also holds that node \(t\) in \(T_{R}\) is a \(1\)- or a \(2\)-node, since node \(t\) was a \(1\)- or a \(2\)-node in \(T_{OPT}\), as well. Let \(A=V(G)\setminus(Z\cup\{u\})\).