  A set $X \subseteq V(G)$ in a graph $G$ is $(q,k)$-unbreakable if every
separation $(A,B)$ of order at most $k$ in $G$ satisfies $|A \cap X| \leq q$ or
$|B \cap X| \leq q$. In this paper, we prove the following result: If a graph
$G$ excludes a fixed complete graph $K_h$ as a minor and satisfies certain
unbreakability guarantees, then $G$ is almost rigid in the following sense: the
vertices of $G$ can be partitioned in an isomorphism-invariant way into a part
inducing a graph of bounded treewidth and a part that admits a small
isomorphism-invariant family of labelings. This result is the key ingredient in
the fixed-parameter algorithm for Graph Isomorphism parameterized by the
Hadwiger number of the graph, which is presented in a companion paper.
