2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Oct 11, 2023 at 15:32

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Hi ! could you clarify once more why number of edges between any $v_i$ and S came out to be even ?? $\endgroup$
    – Snowflake
    Oct 12, 2023 at 8:21
  • $\begingroup$ Hi @OmJoglekar. No problem! That part of my answer was definitely a bit terse. I have added some more details for that part. $\endgroup$ Oct 12, 2023 at 13:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .