= Solution
A valid <triangulation of an undirected graph> adds exactly the two fill edges
$$
\boxed{AC\quad\text{and}\quad AM.}
$$
To verify it, eliminate the vertices in the order $P,Q,R,S,X,Y,B,D,F,M,A,C,U,V$. The first eight eliminations have neighboring vertices already joined. When $F$ is eliminated, its remaining neighbors are $A,M$, so add $AM$. When $M$ is eliminated, its remaining neighbors are $A,C$, so add $AC$. The remaining $A,C,U,V$ form a <clique>.
Thus this order is a <perfect elimination ordering> of the completed graph, which is a <chordal graph>. The fill edges are computational devices for genotype elimination; they do not add parent-child relationships to the <pedigree>.
Back to article page
