So, this is not an example of using linear programming duality within a proof of a theorem but, rather, an example of using linear programming duality to search for a proof.
The discharging method is a technique which is often used to prove structural results for planar graphs (among other applications). Perhaps the most famous application of the discharging method is in the proof of the Four Colour Theorem.
In the discharging method, one assigns each vertex, face, and edge to a "charge" so that the sum of the charges is negative (by Euler's Polyhedral Formula). Then, magically, one shows that, in a minimal counterexample to the theorem, it is possible to redistribute the charge in such a way that the total sum of the charges is preserved and every vertex, face and edge ends up with non-negative charge. This contradicts the fact that the sum of the charges is negative.
An example of a possible initial charge is to assign every edge a charge of zero, every vertex $v$ a charge of $d(v)-4$ and every face $f$ a charge $d(f)-4$ where $d(v)$ and $d(f)$ denote the degree of $v$ and $f$, respectively. Using Euler's Polyhedral Formula, its easy to see that the sum of the charges is $-8$.
Now, how does linear programming come in? First, we need to determine what types of redistribution rules we want. For example, we may have rules of the form:
(1) Every vertex of degree $5$ transfers charge $x_{5,3}\geq0$ to every triangular face that contains it.
(2) Every face of degree $6$ or larger transfers charge $y_{6,3}\geq0$ to each vertex of degree $3$ on its boundary.
Etc.
These rules will provide us with a collection of variables. We form the constraints by insisting that the final charge of each vertex, face and edge is non-negative. For example, if $v$ is a vertex of degree $5$, then the initial charge of $v$ is $d(v)-4=1$. If $v$ is contained in $5$ triangles and, if the charge of such vertices is only affected by rule (1) above, then one of our constraints would be
$1 - 5x_{5,3}\geq 0$.
If there is a feasible point for all of our constraints, then we are done. If not, our goal is to show that some subset of the constraints cannot appear if $G$ is a minimal counterexample to the theorem. We complete the definition of the linear program by asking it to maximise an objective function which is equal to the minimum final charge of any vertex, edge or face "type."
Now, take the dual and solve it. If the solution to the dual is positive, then this implies that there is a feasible point for the primal, which gives us our redistribution rules. If the solution to the dual is negative, we determine the point at which the dual is minimised. This gives us a set of constraints in the primal which cannot all be satisfied simultaneously. So, in order to obtain the discharging proof, we need to prove that one of these substructures cannot exist in a minimal counterexample (i.e. it is a reducible configuration). Once we have done this, we can remove the corresponding constraint from the program and run the dual again, and repeat this procedure until we have a discharging proof!
Apologies for the lengthy explanation, but hopefully it is useful for someone. Some additional explanation can be found in Section 3 of this paper and in this paper.