1

Suppose there is a simple graph, and each vertices are colored white at the beginning. Now you can do the following operation, select a vertex, and flip the color of it and it's adjacent vertices. (White->Black, Black->White)

Now I want to show that I can always flip the color to black for all vertices.

This problem can be also viewed as the following: The 0,1 adjacent matrix $G$ (satisfy $G_{ii}=1$) of a simple graph contains $(1,...,1)$ in the range space in $F_2$. But I don't know how to prove it if $G$ is not invertable.

Either linear algebra or combinatorial proof are welcome.

Tianhao
  • 11
  • I had to read your next to final paragraph more than once to see your point. You consider the adjacency matrix of the graph plus the identity matrix(?) to get ones on the diagonal. Perhaps an example would make your idea clearer for many Readers. – hardmath Sep 07 '22 at 19:02
  • Yeah, your understanding is correct. I found the answer already, and it requires to use the identity Im(G) = perp(ker G^T), so directly check that the all one vector is perpendicular to the ker G suffice. – Tianhao Sep 07 '22 at 19:15
  • Here is a brief introduction to posting mathematical notation. Note that the adjacency matrix of a simple graph is symmetric, and it would follow that $G^T = G$. – hardmath Sep 07 '22 at 20:32

0 Answers0