  Given a graph $G$ with vertices $\{v_1,\ldots,v_n\}$, we define
$\mathcal{S}(G)$ to be the set of symmetric matrices $A=[a_{i,j}]$ such that
for $i\ne j$ we have $a_{i,j}\ne 0$ if and only if $v_iv_j\in E(G)$. Motivated
by the Graph Complement Conjecture, we say that a graph $G$ is complementary
vanishing if there exist matrices $A \in \mathcal{S}(G)$ and $B \in
\mathcal{S}(\overline{G})$ such that $AB=O$. We provide combinatorial
conditions for when a graph is or is not complementary vanishing, and we
characterize which graphs are complementary vanishing in terms of certain
minimal complementary vanishing graphs. In addition to this, we determine which
graphs on at most $8$ vertices are complementary vanishing.
