  The singularity degree of a semidefinite programming problem is the smallest
number of facial reduction steps to make the problem strictly feasible. We
introduce two new graph parameters, called the singularity degree and the
nondegenerate singularity degree, based on the singularity degree of the
positive semidefinite matrix completion problem. We give a characterization of
the class of graphs whose parameter value is equal to one for each parameter.
Specifically, we show that the singularity degree of a graph is equal to one if
and only if the graph is chordal, and the nondegenerate singularity degree of a
graph is equal to one if and only if the graph is the clique sum of chordal
graphs and $K_4$-minor free graphs. We also show that the singularity degree is
bounded by two if the treewidth is bounded by two, and exhibit a family of
graphs with treewidth three, whose singularity degree grows linearly in the
number of vertices.
