What is the parity of the determinant of the adjacency matrix of a graph with an odd number of vertices?

Question

A graph $G$ has an odd vertices and $A$ is a adjacency matrix of graph $G$ , how show $$\det (A)\equiv 0\pmod 2.$$

Answer 1

Let $n$ be the number of vertices of the (simple) graph. Then the adjacency matrix $A$ is a $n\times n$ symmetric matrix, with integer entries, and with zeros along the main diagonal.

Let $S$ be the matrix obtained from $A$ by replacing any element $a_{ij}$ with $i<j$ by $−a_{ij}$. Of course $\det(A)\equiv \det(S)\pmod{2}$. Moreover the $S$ is skew-symmetric, that is $S^t=-S$ and therefore $$\det(S)=\det(S^t)=\det(-S)=(-1)^n\det (S)=-\det(S)\implies \det(S)=0.$$ Since $\det(A)$ and $\det(S)=0$ have the same parity, we may conclude that $\det(A)$ is even.

Answer 2

If $m$ is the number of edges then we have

• $$ \sum _{i=1}^{n} \lambda_{i} ^{2} = 2 m$$
• $$ \det(A) = \prod _{i=1}^{n} \lambda _{i} $$ suppose all of the $\lambda_{i} $ is odd then contradiction 1 then there exist a $\lambda_{k}$ that even so $$ \det (A) \equiv 0 \pmod 2 $$

Answer 3

Eigenvalues of $A$ must be integer or irrational number.

• Suppose all $\lambda_{i}$s are integer: then one $\lambda_{i}$ must be even. because: $\sum _{i=1}^{n} \lambda_{i} = 0$ , $n \equiv 1 \pmod 2$.

• Suppose at least one $\lambda_{i}$ is irrational ($\lambda_{1}$): We know that sum of irrational numbers is irrational, and $\sum _{i=1}^{n} \lambda_{i} = 0$. Then exists other irrational number ($\lambda_{2}$) : $k_{1}.|\lambda_{1}| = k_{2}.|\lambda_{2}|$ and $k_{1}, k_{2}$ is integer and $\lambda_{1}. \lambda_{2} \lt 0$.

  If $k_{1} \equiv k_{2} \pmod 2$ then exist one even integer number ($\lambda_{3}$). else suppose $k_{1} \equiv 0\pmod 2$ then $\lambda_{2} ^ {2} \equiv 0 \pmod 2$.

  We know $\lambda_{i} ^{2}$ must be integer ($\sum _{i=1}^{n} \lambda_{i} ^{2} = 2m$). If $k_{2} > 1$ then $\lambda_{2} ^{2} $ is in $det A$ and problem solved. If $k_{2} = 1$ then $k_{1} ^ {2}.|\lambda_{1}|^{2} = |\lambda_{2}|^ 2$ and it means $k_{1} | \lambda_{2}$ but $\lambda_{2}$ is irrational, which is a contradiction.