Post Made Community Wiki by S. Carnahan
2 deleted 48 characters in body

I (think) that the classification theorem of Chudnovsky, Robertson, Seymour and Thomas for perfect Berge graphs qualifies. Namely, their strategy for proving the Strong perfect graph theorem was to prove the following theorem.

Theorem. Let $G$ be a Berge graph. Then at least one of the following holds:

1. $G$ (or its complement) is bipartite.
2. $G$ (or its complement) is the line graph of a bipartite graph.
3. $G$ is a double-split graph.
4. $G$ (or its complement) admits a proper 2-join.
5. $G$ admits a balanced skew partition.
6. $G$ admits a homogenous pair.

For definitions of these terms, see the proof of the Strong perfect graph theorem.

It turns out that this structure theorem is sufficient to prove the Strong perfect graph theorem since one can prove that bipartite graphs, line graphs of bipartite graphs and double-split graphs are perfect and a minimal counterexample to the theorem cannot satisfy (4), (5) or (6).

To actually answer the question, Chudnovsky later proved that (6) can be dropped from the above structure theorem. The proof of the improved statement is over 200 pages, so this is a certainly a non-trivial re-categorization. I do admit it is a bit unsatisfying that this re-categorization is just a proper subset of the original categorization.

1

I (think) that the classification theorem of Chudnovsky, Robertson, Seymour and Thomas for perfect graphs qualifies. Namely, their strategy for proving the Strong perfect graph theorem was to prove the following theorem.

Theorem. Let $G$ be a Berge graph. Then at least one of the following holds:

1. $G$ (or its complement) is bipartite.
2. $G$ (or its complement) is the line graph of a bipartite graph.
3. $G$ is a double-split graph.
4. $G$ (or its complement) admits a proper 2-join.
5. $G$ admits a balanced skew partition.
6. $G$ admits a homogenous pair.

For definitions of these terms, see the proof of the Strong perfect graph theorem.

It turns out that this structure theorem is sufficient to prove the Strong perfect graph theorem since one can prove that bipartite graphs, line graphs of bipartite graphs and double-split graphs are perfect and a minimal counterexample to the theorem cannot satisfy (4), (5) or (6).

To actually answer the question, Chudnovsky later proved that (6) can be dropped from the above structure theorem. The proof of the improved statement is over 200 pages, so this is a certainly a non-trivial re-categorization. I do admit it is a bit unsatisfying that this re-categorization is just a proper subset of the original categorization.