Maximum cardinality search

Maximum cardinality search is a graph search in which an unselected vertex's score counts its already selected graph neighbours. Repeatedly select a vertex of maximum score, breaking ties arbitrarily, and update its unselected graph neighbours. On a chordal graph, the reverse selection order is a perfect elimination ordering. On $C_4$, selecting $(a,b,c,d)$ instead yields candidate deletion order $(d,c,b,a)$; $d$'s later graph neighbours $a,c$ are not adjacent, so the clique check fails.^[ref]