To prove this, we show that the set of universally stable graphs is closed under the taking of minors; polynomial-time decidability then follows from results of Robertson and Seymour [1986; 1990].

A natural next question is whether one can characterize the set of universally stable graphs. We show that for undirected graphs, there is a polynomial-time algorithm that decides universal stability.

The crucial fact we show here is that the family of universally stable graphs is a minor-closed set; this is what allows us to apply the results of Robertson and Seymour [1995].

Our objective is to show that the set of universally stable graphs is minor-closed.