Reading through the paper Algorithmic Aspects of Vertex Elimination on Directed graphs. There 's a detail in Lemma 3 which I don't know why it would be guaranteed to be true.
Most of the terminology used I think is standard so I won't write definition if that's not the case let me know and I'll write the needed definitions.
The paper is about graph technique applied to symbolic factorization of sparse matrices, specifically when applying Gauss-Elimination.
Let $G = (V,E)$ be a perfect elimination graph. Suppose $F \neq \emptyset$ is a fill-in for $G$. Let $G' = (V, U \cup F)$. Then $\exists f \in F$ such that $G' - f = (V, E \cup (F - \left\{ f \right\}))$ is a perfect elimination (i.e. F - $\left\{ f \right\}$ is a fill in.
Proof: We prove the lemma by inducition on $n = |V|$. If $n \leq 2$ the results is obvious since any graph with one or two vertices is a perfect elimination. Suppose the result is true for all $n \neq n_0$ and let $n = n_0 + 1$. Let $R = \left\{ x : D(x) = \emptyset \right\}$ where $D(x)$ is the deficiency in $G$ and let $S = \left\{ x : D'(x) \neq \emptyset \right\}$ where $D'(x)$ is the deficiency in $G'$. We know $R \neq \emptyset$ and $S \neq \emptyset$.
Why are $R$ and $S$ for sure not empty?