Let $G$ be a simple graph with vertex set $\{v_1,v_2,\ldots,v_n\}$. The adjacency matrix of $G$ is the 0-1 matrix $A$, where $A_{i,j}=1$ when $v_i$ is adjacent with $v_j$. The degree matrix is the diagonal matrix $D$ where $D_{i,i}$ is the degree of $v_i$.

It seems that for any graph $G$, the sum of elements in any product of any $A$'s and any $D$'s (in any order) is always even. Can any one give a proof for this observation? Is it a known result? Note that the sum of elements in any power of $A$ (or $D$ ) is even, giving the first evidence to the above observation.

For example, consider $$A= \left( \begin{matrix} 0&0&1&1\\ 0&0&1&0\\ 1&1&0&1\\ 1&0&1&0\\ \end{matrix} \right), D=\left( \begin{matrix} 2&0&0&0\\ 0&1&0&0\\ 0&0&3&0\\ 0&0&0&2\\ \end{matrix} \right).$$ One can verifies that $e^TAe=8,e^TDe=8,\ldots,e^TADAAADe=422,\ldots$ are all even, where $e=(1,1,1,1)^T$.


1 Answer 1


I think this is false.

Here is a graph and some code in Sage to compute the sum of elements of $AADAAD$ which appears to be odd.

8-vertex graph

I tried to prove it for a while, failed, so then decided to try some randomised searching on smallish graphs.

x = Graph('G?B@dW')
A = x.adjacency_matrix()
D = matrix.diagonal([x.degree(v) for v in x.vertices()])
j = matrix([1 for i in range(x.num_verts())])
  • $\begingroup$ Thanks for your reply. It seems that the parity of sums depends heavily on strings chosen. In some cases, the results are always even. I have failed to find even a counterexample using Mathematica. Maybe I used some bad strings such as 'ADAAD'. When I change it to AADAAD as you suggested, it does give a few graphs with sums odd. Thanks again. $\endgroup$
    – W. Wang
    Aug 22, 2019 at 15:28
  • 1
    $\begingroup$ At first sight I thought that the statement should either be obviously true or obviously false, so the fact that it took a little effort to find a counterexample makes me wonder if there is something interesting there. $\endgroup$ Aug 23, 2019 at 1:06
  • $\begingroup$ The entries of such products are counting homomorphisms from a graph $H$ determined by the string to the fixed graph $G$. So if the number of homomorphisms from $H$ to $G$ is even independent of $G$ (e.g., if $H$ is just an edge), then the sum of the entries will be even. To determine $H$, let $K_2$ be a complete graph on the two vertices $a$ and $b$. Then $A_{uv}$ is the number of homomorphisms from $K_2$ to $G$ where $a,b$ get mapped to $u,v$ respectively, and $D_{uv}$ is the number of homomorphisms where $a,a$ gets mapped to $u,v$ respectively (thus the zeros off the diagonal). $\endgroup$ Aug 24, 2019 at 15:43
  • $\begingroup$ For products see here: mathoverflow.net/questions/335072/… $\endgroup$ Aug 24, 2019 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.