  We show that the problem of counting perfect matchings remains #P-complete
even if we restrict the input to very dense graphs, proving the conjecture in
[5]. Here "dense graphs" refer to bipartite graphs of bipartite independence
number $\leq 2$, or general graphs of independence number $\leq 2$. Our proof
is by reduction from counting perfect matchings in bipartite graphs, via
elementary linear algebra tricks and graph constructions.
