The $c_2$-invariant is an arithmetic graph invariant useful for understanding Feynman periods. Brown and Schnetz conjectured that the $c_2$-invariant has a particular symmetry known as completion invariance. This paper will prove completion invariance of the $c_2$-invariant in the $p=2$ case, extending previous work of one of us. The methods are combinatorial and enumerative involving counting certain partitions of the edges of the graph.