A curious asymmetry in good characterizations

Question

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:

1. 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.

2. 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.

Answer 1

(This is to answer Sasho Nikolov's comment, but it is way too long for the comment field, so I post it as an answer.)

The two examples in the original question are special cases of LP duality. There are many similar examples, but one can argue that they all inherit the asymmetry from LP duality. Weak LP duality is easy to prove (it provides the "trivial obstacle"), while strong duality is deeper, proving that the trivial obstacle is the only obstacle. In this sense, the examples that are "children of LP" may be viewed that they are only different incarnations of the same core example.

Here are, however, some other cases that (to my knowledge) are not related to LP. The examples below are all from graph theory, but other fields probably also contain similar patterns.

1. Let $k, l, d$ be positive integers. Then there is a simple graph with vertex-connectivity $k$, edge-connectivity $l$, and minimum degree $d$, if and only if $k\leq l \leq d$. Since it is (almost) trivial to prove that these parameters always satisfy the inequalities, the violation of at least one inequality is a trivial obstacle for such a graph to exist. The other direction, that such a graph always exists is nontrivial. (See the book of Bollobas "Extremal Graph Theory," Theorem 1.5. Note: the way it is presented there is somewhat more complicated, using more inequalities, because it also uses another parameter, the number of vertices. But this simpler version can be extracted from it, to show the essential nature that here again the trivial obstacle is the only obstacle.)

2. Given an undirected simple graph, does it have two vertex-disjoint circuits? This is answered by the following theorem of Lovasz and Dirac: If a simple graph with minimum degree $\geq 3$ does not have two vertex-disjoint circuits, then the graph can only be one of the following three types: (1) $K_5$, (2) a wheel graph, (3) $K_{3,n-3}$, with possibly any edges added to the the 3-vertex class. Here the trivial obstacle is that the graph falls into one of these types, since these types are easily seen not to contain 2 vertex-disjoint circuits. If the trivial obstacle is absent, the graph always has the property (but it is quite nontrivial to prove).

3. Given a sequence $d_1\geq\ldots\geq d_n$ of integers, and an integer $k\geq 2$, does there exist a $k$-edge connected simple graph that has $d_1\geq\ldots\geq d_n$ as its degree sequence? A 1964 result of Edmonds answers the question: such a graph exists if and only if two conditions hold: (a) the sequence is graphical (i.e., there is a graph at all that implements it as a degree sequence, which is trivially necessary, and can be checked by the Erdos-Gallai Theorem), and (b) $d_n\geq k$, which is also trivially necessary, since the edge connectivity is bounded from above by the minimum degree. Once these essentially trivial necessary conditions are satisfied, the desired graph always exists.

4. Given a complete graph $G$, and a fixed graph $H$, can the edges of $G$ be partitioned into disjoint copies of $H$? A 1976 theorem of Wilson proves that if $G$ is sufficiently large, then the only obstacle for such a partition to exist is the violation of one the following trivially necessary divisibility conditions: (a) $|E(H)|$ is a divisor of $|E(G)|$, (b) if $g$ is the greatest common divisor of the degrees of $H$, then $g$ is a divisor of $|V(G)|-1$.