Hard-looking algorithmic problems made easy by theorems
If I understand your question correctly, a canonical example would be deciding if a graph $G$ has an Eulerian circuit: equivalent to checking that $G$ is connected and every vertex has even degree.