# Adding a Tail in Classes of Perfect Graphs
## 5 \(P_{4}\)-Sparse Graphs
Note that there is no set \(V_{j}\) such that \(x\in V_{j}\cap A\), \(y\in V_{j}\cap Z\) and \(x\) is a neighbor of \(u\) in \(G\); otherwise, we can move \(x\) to \(Z\) together with \(y\); because \(y\) is in \(Z\), all adjacencies from \(y\) to all the vertices in \(V(G)\setminus(V_{j}\cup\{u\})\) in \(G\) are maintained and this will also hold for \(x\) and the fill edge \(xw\) will be removed, a contradiction to the optimality of \(G_{R}\). Similarly, there is no set \(V_{j}\) such that \(x\in V_{j}\cap A\), \(y\in V_{j}\cap Z\) and \(y\) is a non-neighbor of \(u\) in \(G\); otherwise, we can move \(y\) to \(A\) together with \(x\), thus omitting the fill edge \(uy\). This implies that for each \(i=0,1,\ldots,h\), either \(V_{i}\subseteq A\) or \(V_{i}\subseteq Z\) and since \(t=t_{k}\), \(V_{k}\subseteq Z\). Finally, there exists no \(j>k\) such that \(V_{j}\subseteq A\). Suppose that there existed such a \(V_{j}\) and let \(j\) be the largest such index. Then, because \(t=t_{k}\) is a \(1\)- or a \(2\)-node and \(k<j\), there would exist a vertex \(z\in V_{k}\) which would be adjacent to all vertices in \(V_{j}\). This implies that in \(T_{R}\), the least common ancestor of \(z\) and the vertices in \(V_{k}\) would be a \(1\)-node; thus, \(u\) and \(w\) would be adjacent to all vertices in \(V_{j}\) and if we moved \(V_{j}\) to \(Z\) then we would have fewer fill edges, a contradiction to the optimality of \(G_{R}\). Therefore, the tree \(T_{R}\) is as described in Case 3 of the statement of the lemma. 1. The leaves associated with \(u,w\) in \(T_{OPT}\) have the same parent node \(p\): Then, since \(u,w\) are adjacent, the parent node \(p\) is either a \(1\)-node or a \(2\)-node. 1. _The parent node \(p\) of \(u,w\) in \(T_{OPT}\) is a \(1\)-node_: Then, the leaves associated with \(u\) and \(w\) are the only children of \(p\) (Formation 1): otherwise, we can use Formation 2 as shown in Figure 8 which requires fewer fill edges. Then, \(w\) will be adjacent to all neighbors of \(u\) in \(T_{OPT}\); this and the optimality of \(G_{OPT}\) imply that \(T_{OPT}\) results from \(T_{G}\) by replacing the leaf for \(u\) by Formation 1. 2. _The parent node \(p\) of \(u,w\) in \(T_{OPT}\) is a \(2\)-node_: Let \(H=(S,K,R)\) be the corresponding spider. If \(H\) is thick (thus \(|K|\geq 3\)), then no matter whether the tail \(uw\) is an \(S\)-\(K\), \(K\)-\(K\) or \(R\)-\(K\) edge, the sum of degrees of \(u,w\) in \(H\) (excluding \(uw\)) is at least \(|V(H)|-3+|K|-2\) (consider an \(S\)-\(K\) edge). However, we would have added no more fill edges if we had made \(u\) universal in \(G[V(H)\setminus\{w\}]\) and then applied Formation 2 at the parent of the leaf for \(u\) (then \(Z=V(H)\setminus\{u,w\}\)) using \(|V(H)|-2\leq|V(H)|+|K|-5\) fill edges. In the same way, we show that we would have added no more fill edges if \(H\) were a thin spider and the tail \(uw\) were a \(K\)-\(K\) or \(K\)-\(R\) edge. Then, either \(u\in K\) and \(w\in S\) or \(u\in S\) and \(w\in K\); in the latter case, we exchange \(u\) and \(w\) for the same total number of fill edges and obtain \(u\in K\) and \(w\in S\) again. Figure 7: **(left)** The \(P_{4}\)-sparse tree \(T_{OPT}\) in which the leaves for \(u,w\) do not have the same parent node and have node \(t\) as their least common ancestor; **(right)** The \(P_{4}\)-sparse tree \(T_{R}\) obtained by using Formation 2 just above node \(t\) which results in no more fill edges than those in \(G_{OPT}\).