Long-Standing Conjectures later trivially proved by an implication

Question

I'd like to know if there have been conjectures that have long been unproven in TCS, that were later proven by an implication from another theorem, that may have been easier to prove.

Answer 1

Erdös and Pósa proved that for any integer $k$ and any graph $G$ either $G$ has $k$ disjoint cycles or there is a set of size at most $f(k)$ vertices $S\in G$ such that $G\setminus S$ is a forest. (in their proof $f(k) \in O(k \cdot \log k)$).

The Erdös and Pósa property of a fixed graph $H$ known as the following (not a formal definition):

The class of graphs $\mathcal{C}$ admits the Erdös-Pósa property if there is a function $f$ such that for every graph $H\in \mathcal{C}$ and for any $k \in \mathbb{Z}$ and for any graph $G$ either there are $k$ disjoint isomorphic copy (w.r.t minor or subdivision) of $H$ in $G$ or there is a set of vertices $S\in G$, such that $|S|\le f(k)$ and $G\setminus S$ has no isomorphic copy of $H$.

After Erdös and Pósa's result for a class of cycles which are admitting this property, it was an open question to find a proper class $\mathcal{C}$. In graph minor V proved that every planar graph either has a bounded tree width or contains a big grid as a minor, by having the grid theorem in hand they showed that Erdös and Pósa property holds (for minor) if and only if $\mathcal{C}$ is a class of planar graphs. The problem still is open for subdivision, though. But the proof of theorem w.r.t minor is somehow simple and as best of my knowledge there is no proof without using the grid theorem.

Recent results for digraphs, provides answers for long standing open questions in the similar area for digraphs. e.g one very basic question was that is there a function $f$ such that for any graph $G$ and integers $k,l$, we either can find a set $S\subseteq V(G)$ of at most $f(k+l)$ vertices such that $G-S$ has no cycle of length at least $l$ or there are $k$ disjoint cycles of length at least $l$ in $G$. This is only a special case but for $l=2$ it was known as a Younger's conjecture. Before that Younger's conjecture was proven by Reed et al with quite a complicated approach.

It's worth to mention that still there are some quite non-trivial cases in digraphs. e.g Theorem 5.6 in the above paper is just a positive extension of younger's conjecture to a small class of weakly connected digraphs, but with the knowledge and mathematical tools that we have it's not trivial (or maybe we don't know a simple argument for that). Perhaps by providing a better characterisation for those graphs, there will be an easier way to prove it.

Answer 2

the title of the question refers to "trivial implications" but the contents do not exactly specify that criteria, so this is a bit of a mixed message. one semifamous item/ example that comes close to the general theme is the proof of the (then ~4 decade old) Strong Perfect Graph Conjecture in 2002 by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. the problem of algorithmic complexity of recognition of perfect graphs turned out to be closely tied/ tightly to the proof mechanics of the strong perfect graph conjecture, although this was not exactly well understood or known prior to the proof of the conjecture. in other words there was an informal open conjecture that "perfect graph recognition is in P" (or "low complexity" etc) relatively quickly resolved by building on the analysis/ properties/ mechanics of the strong perfect graph theorem.

A polynomial algorithm for recognizing perfect graphs Gérard Cornuéjols, Xinming Liu, Kristina Vušković 2003