There are quite a few theorems, mostly in graph theory and combinatorial optimization, that are often referred to as good characterizations. They typically put a property in $NP\cap co-NP$, by showing that a property either holds, or else there is some well identified obstacle that prevents it from holding. Often they are presented as min-max theorems, see the earlier question Optimization problems with good characterization, but no polynomial-time algorithm Here are two classical examples of good characterizations:A bipartite graph either has a matching of size $k$, or else there are less than $k$ vertices that cover all edges. The existence of such a cover is a trivial obstacle that excludes the matching. If this obstacle is not there, the matching must exist, this is the nontrivial part, known as Konig's Theorem. Either there is an $s-t$ flow of value $F$ in a flow graph, or else there is an $s-t$ cut with capacity less than $F$. Again, the existence of such a cut is a trivial obstacle, since then the flow cannot get through. The nontrivial part is that the absence of the obstacle already guarantees the existence of the flow of value $F$, which is equivalent to the Max Flow Min Cut Theorem. What I find a curious feature in these (and many other) results is that they show a well visible  asymmetry in the proof hardness between the two directions of the equivalence. Usually, it is easy, or even trivial, to prove that the obstacle excludes the considered property. On the other hand, it is much harder to prove that the easy/trivial obstacle is the only obstacle, in the sense that once it is not there, the property must hold. I am not aware of  a good explanation why this type of asymmetry is so common. It does not appear a priori necessary. Note: do not get misled by the fact that the above examples are both special cases of linear programming duality. There are other examples that have nothing to do with linear programming.Question: Do you know any good characterization that does not fall in this category? (Admittedly, it is vaguely defined, but perhaps the idea got through.) In other words, I am looking for a theorem that puts a property in $NP\cap co-NP$, by capturing all possible obstacles of the property, but they are not all easy/trivial obstacles.
A curious asymmetry in good characterizations
cc.complexity theory;graph theory;co.combinatorics