# Existence of a subset S of the set of vertices of a graph given number of walks between any two vertices of some length $l$ are odd

As the title says,

Let G be a simple graph with at least 2 vertices. Suppose for some $$l\geq 1$$ the number of walks of length $$l$$ between any two vertices of the graph (not necessarily distinct!) is odd. Show that there exists a subset of the vertices of G $$S \subseteq V(G)$$ such that S has an even number of vertices and each vertex of G is adjacent to an even number of vertices in S

My progress so far:

All entries of $$(A_G)^l$$ must be odd because we know that the $$(i,j)-th$$ entry of the matrix $$(A_G)^l$$ (where $$A_G$$ is the adjacency matrix of G) is equal to the number of walks of length $$l$$ between vertices $$v_i$$ and $$v_j$$

I have no idea what to make of the 'all odd entries' matrix

Any guidance on this will be much appreciated

Edit : Choosing S to be empty is trivial. Although Stanley doesn't mention that S has to be non trivial, I don't think he wants us to find the trivial one

• This is a funny question. I bet you can do all kinds of linear algebra over $\Bbb F_2$ to find out about this matrix. However I don't understand what's stopping you from just letting $S$ be the empty set. Is that allowed? Oct 11, 2023 at 15:32

Here's the linear algebra. Working over $$\Bbb F_2$$, we see $$A^l$$ is the all-ones matrix, which is singular. Its kernel is exactly the set of vectors $$y$$ for which $$(1, 1, \dotsc, 1)y = 0$$, ie which have an even number of ones. Since $$A^l$$ is singular, $$A$$ must also be singular, so there is some nonzero vector $$x$$ in its kernel. But it's also in the kernel of $$A^l$$, so it has an even number of ones.
Now note $$x$$ defines some subset $$S$$ of the vertices as follows: if we say the vertices are $$v_1, \dotsc, v_n$$ and the standard basis vectors corresponding to these vertices are $$e_1, \dotsc, v_n$$, then $$x = \sum_{v_i \in S} e_i$$ for some unique set $$S$$ ("the set of vertices for which $$x$$ has a $$1$$ at that position"). $$S$$ consists of an even number of vertices, because we know that $$x$$ is in the kernel of $$A^l$$.
For any $$i$$, we have $$e_i^{\mathsf T} A x = 0$$ (because $$Ax = 0$$), and hence by expanding $$x$$, we have $$\sum_{v_j \in S} e_i^{\mathsf T} A e_j = 0$$, and hence $$\sum_{v_j \in S} A_{ij} = 0$$. This says that modulo $$2$$, the number of edges between $$v_i$$ and vertices $$v_j$$ in $$S$$ is $$0$$, or in other words, the number of such edges is even.
• Hi ! could you clarify once more why number of edges between any $v_i$ and S came out to be even ?? Oct 12, 2023 at 8:21