  We prove that all Gibbs measures of the $q$-state Potts model on
$\mathbb{Z}^2$ are linear combinations of the extremal measures obtained as
thermodynamic limits under free or monochromatic boundary conditions. In
particular all Gibbs measures are invariant under translations. This statement
is new at points of first-order phase transition, that is at $T=T_{c}(q)$ when
$q>4$. In this case the structure of Gibbs measures is the most complex in the
sense that there exist $q+1$ distinct extremal measures.
  Most of the work is devoted to the FK-percolation model on $\mathbb{Z}^{2}$
with $q\geq 1$, where we prove that every Gibbs measure is a linear combination
of the free and wired ones. The arguments are non-quantitative and follow the
spirit of the seminal works of Aizenman and Higuchi, which established the
Gibbs structure for the two-dimensional Ising model. Infinite-range
dependencies in FK-percolation (i.e., a weaker spatial Markov property) pose
serious additional difficulties compared to the case of the Ising model. For
example, it is not automatic, albeit true, that thermodynamic limits are Gibbs.
The result for the Potts model is then derived using the Edwards-Sokal coupling
and auto-duality. The latter ingredient is necessary since applying the
Edwards-Sokal procedure to a Gibbs measure for the Potts model does not
automatically produce a Gibbs measure for FK-percolation.
  Finally, the proof is generic enough to adapt to the FK-percolation and Potts
models on the triangular and hexagonal lattices and to the loop $O(n)$ model in
the range of parameters for which its spin representation is positively
associated.
