Hard-looking algorithmic problems made easy by theorems I am looking for nice examples, where the following phenomenon occurs: (1) An algorithmic problem looks hard, if you want to solve it working from the definitions and using standard results only.
(2) On the other hand,  it becomes easy, if you know some (not so standard) theorems. 

The goal of this is to illustrate for students that learning more theorems can be  useful, even for those  who are outside of the theory field (such as software engineers, computer engineers etc). Here is an  example: 


   Question:  Given integers $n, k, l, d$, does there exist an $n$-vertex graph (and if so, find one), such that its vertex connectivity is $k$, its edge connectivity is $l$, and its minimum degree is $d$? 


Note that we require that the parameters are exactly equal to the given numbers, they are not just bounds. If you want to solve this from scratch, it might appear rather hard. On the other hand, if you are familiar with the following theorem (see  Extremal Graph Theory  by B. Bollobas), the situation becomes quite different.


  Theorem:  Let $n, k, l, d$ be integers. There exists an $n$-vertex graph with vertex connectivity $k$, edge connectivity $l$, and minimum degree  $d$, if and only if one of the following conditions is satisfied: 
    $0\leq k\leq l \leq d &lt;\lfloor n/2 \rfloor$, 
   $1\leq 2d+2-n\leq k\leq l = d&lt; n-1$
   $k=l=d=n-1.$
  


These conditions are very easy to check, being simple  inequalities among the input parameters, so the existence question can be answered effortlessly. Furthermore, the proof of the theorem is constructive, resolving the construction issue, as well. On the other hand, this result does not appear standard enough, so that you can expect everybody to know about it.

Can you provide further examples in this spirit, where knowing a (not so standard) theorem greatly simplifies a task?
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.