  A $k$-pairable $n$-qubit state is a resource state that allows Local
Operations and Classical Communication (LOCC) protocols to generate EPR-pairs
among any $k$-disjoint pairs of the $n$ qubits. Bravyi et al. introduced a
family of $k$-pairable $n$-qubit states, where $n$ grows exponentially with
$k$. Our primary contribution is to establish the existence of 'small' pairable
quantum states. Specifically, we present a family of $k$-pairable $n$-qubit
graph states, where $n$ is polynomial in $k$, namely $n=O(k^3\ln^3k)$. Our
construction relies on probabilistic methods. Furthermore, we provide an upper
bound on the pairability of any arbitrary quantum state based on the support of
any local unitary transformation that has the shared state as a fixed point.
This lower bound implies that the pairability of a graph state is at most half
of the minimum degree up to local complementation of the underlying graph,
i.e., $k(|G \rangle)\le \lceil \delta_{loc}(G)/2\rceil$. We also investigate
the related combinatorial problem of $k$-vertex-minor-universality: a graph $G$
is $k$-vertex-minor-universal if any graph on any $k$ of its vertices is a
vertex-minor of $G$. When a graph is $2k$-vertex-minor-universal, the
corresponding graph state is $k$-pairable. More precisely, one can create not
only EPR-pairs but also any stabilizer state on any $2k$ qubits through local
operations and classical communication. We establish the existence of
$k$-vertex-minor-universal graphs of order $O(k^4 \ln k)$. Finally, we explore
a natural extension of pairability in the presence of errors or malicious
parties and show that vertex-minor-universality ensures a robust form of
pairability.
