my solution from test

My problem! The above is easily the cleanest solution (plus it was found during the exam). Here is my original solution: We first put the problem in graph theoretic terms: Consider a finite simple graph $G$. A walk of length $2022$ is called mischievous if the degree of its starting vertex is odd, and the degree of its ending vertex is even. Prove that the total number of mischievous walks is even. Let $2022=m$. We prove the problem for all positive integers $m$. Denote the number of mischevous walks by $S$. Let $V$ be the vertex set of the graph. For any two distinct vertices $u,v$ let $f(u,v)$ denote the number of walks of length $m$ with starting vertex $u$ and ending vertex $v$. Note that $f(u,v)=f(v,u)$. Then $$S=\sum_{\substack{\deg(u) \ \text{odd} \\ \deg(v) \ \text{even}}}f(u,v)$$We can also write the above sum as sum over all unordered pairs $\{u,v\}$ such that $\deg(u), \deg(v)$ have different parities. Note that $\deg(u), \deg(v)$ have different parities $\iff$ $\deg(u)+\deg(v) \equiv 1 \pmod{2}$. Hence we can write the following equalities: ($\{u,v\}$ denotes unordered pair, while $(u,v)$ denotes ordered pair) \begin{align*} S \ & \equiv \sum_{\substack{\{u,v\} \in V \\ u \neq v}}f(u,v)(\deg(u)+\deg(v)) \pmod{2} \\ &= \ \frac12 \sum_{\substack{(u,v) \in V \times V \\ u\neq v}}f(u,v)(\deg(u)+\deg(v)) \\ &= \ \frac12 \left(\sum_{\substack{(u,v) \in V \times V \\ u\neq v}}f(v,u)\deg(u)+\sum_{\substack{(u,v) \in V \times V \\ u\neq v}}f(u,v)\deg(v) \right) \\ &= \sum_{\substack{(u,v) \in V \times V \\ u \neq v}} f(u,v)\deg(v) \end{align*} Let $R$ denote the RHS. It is sufficient to prove that $R$ is even. Call a walk good if the first vertex and the second-last vertex in the walk are distinct, and bad otherwise. Claim 1: $R$ is the total number of good walks of length $m+1$ in $G$. Proof: Fix a pair of distinct vertices $(u,v)$. Note that we can represent any walk of length $m+1$ as a sequence of its $m+2$ vertices. We will count the number of walks $w_0,w_1 \dots w_m,w_{m+1}$ with $w_0=u$ and $w_m=v$. We can see that the walk $w_0, w_1, \dots w_m$ has $f(u,v)$ choices, while $w_{m+1}$ has $\deg(v)$ choices. Hence number of walks of length $m+1$ with first vertex $u$ and second-last vertex $v \neq u$ is $f(u,v)\deg(v)$. Summing over all pairs $(u,v)$ we get the required expression. $\blacksquare$ Claim 2: Total number of walks of length $k$ in $G$ is even, for any $k \geq 1$. Proof: We prove this statement by induction on $k$. Base case: $k=1$ is true because any walk of length $1$ is just an ordered pair of adjacent vertices, so if $(u,v)$ works so does $(v,u)$. Now assume number of walks of length $k$ are even for all $k \leq n$, for some $n \geq 1$. For any walk of length $n+1$: $w_0,w_1 \dots w_n, w_{n+1}$ we can associate a corresponding walk $w_{n+1},w_n \dots w_1,w_0$ with it. (Basically associate any walk with its reversed counterpart). Note that these two walks are different as long as $w_i \neq w_{n+1-i}$ for some $i$. Thus all such walks can be matched into pairs, so their total number is even. We are left with walks for which $w_i=w_{n+1-i}$ for each $i$, i.e., palindromic walks. These are not possible if $n$ is even since then, $w_{\frac{n}{2}}=w_{\frac{n+2}{2}}$ which is not an edge in our graph. Now, if $n$ is odd then these walks can be uniquely determined by the first $\left \lceil \frac{n+1}{2} \right \rceil$ vertices in the walk, and any walk of length $\left \lceil \frac{n+1}{2} \right \rceil$ gives us a unique palindromic walk of length $n+1$. Thus the number of walks of length $n+1$ has the same parity as number of walks of length $\left \lceil \frac{n+1}{2}\right \rceil \leq n$, which is even by induction hypothesis. $\blacksquare$ Claim 3: Total number of bad walks of length $m+1$ in $G$ is even. Proof: To any bad walk of length $m+1$: $w_0,w_1 \dots w_m, w_{m+1}$ ($w_0 = w_m$) we can associate a corresponding walk $w_m,w_{m-1} \dots w_0,w_{m+1}$ with it. (Basically associate any walk with a walk where the cycled part is reversed). Note that these two walks are different as long as $w_i \neq w_{m-i}$ for some $i$. Thus all such walks can be matched into pairs, so their total number is even. We are left with walks for which $w_i=w_{m-i}$ for each $i$, i.e., walks where the cycled part is palindromic. These bad walks are uniquely determined by the walk $w_{m+1},w_0,w_1 \dots w_{\lceil \frac{m}{2} \rceil}$, and any such walk of length $\left \lceil \frac{m}{2} \right \rceil +1$ gives us a unique bad walk of length $m+1$ where the cycled part is palindromic (it gives us the walk $w_0,w_1 \dots w_{\lceil \frac{m}{2} \rceil},w_{\lceil \frac{m}{2} \rceil-1}, \dots w_0, w_{m+1}$). Thus the number of bad walks of length $m+1$ has the same parity as number of walks of length $\left \lceil \frac{m}{2}\right \rceil +1$, which is even by Claim 2. $\blacksquare$ Claim 2 and Claim 3 give us that the number of good walks of length $m+1$ are even. Therefore by Claim 1, $R$ is even, as required.

Replace $2023$ with $L$ (and the word good with mischievous :p). We re-phrase the problem in Graph Theory terms: "Consider a graph $G$ on $n$ vertices. A walk of length $L$ is good if first edge has odd degree and last edge has even degree. Show that there are an even number of good sequences." Consider a random edge $uv$ in $G$. We induct backwards on the number of edges in $G$. Base case with zero edges is trivial. Case 1: deg $u$, deg $v$ are both odd. Let $V_1, V_2,..., V_L$ and $U_1, U_2,..., U_L$ denote the sets of vertices (with multiplicity) such that $U_i,V_i$ denotes all vertices from whom there exists a walk of length $i$, to $u,v$ (respectively). We don't include $u,v$ in either of $U_L, V_L$. For any $1\leq i\leq L-1$, consider all walks of length $L$ with starting vertex in $U_i$ and ending vertex in $V_{L-i-1}$ and all walks of length $L$ with starting vertex in $V_{L-i-1}$ and ending vertex in $U_i$. The number of such walks is precisely: \[(\#\text{ vertices in }U_i\text{ with odd degree})\cdot(\#\text{ vertices in }V_{L-i-1}\text{ with even degree})\]\[ + (\#\text{ vertices in }U_i\text{ with even degree})\cdot(\#\text{ vertices in }V_{L-i-1}\text{ with odd degree})\] [Note that for $i=L-1$, the number of walks is $(\#\text{ vertices in }U_{L-1}\text{ with even degree}) + (\#\text{ vertices in }V_{L-1}\text{ with even degree})$. So, we may define $U_0={u}$, $V_0={v}$. Similarly, $i=0$ is not an issue.] Now, consider all walks starting from $u$ or $v$ of length $L$. The number of such walks is: \[(\#\text{ vertices in }U_L\text{ with even degree}) \ + \ (\#\text{ vertices in }V_L\text{ with even degree})\]All these walks will simply not exist after edge $uv$ is removed. The number of good walks added after removing edge uv is \[(\#\text{ vertices in }U_L\text{ with odd degree}) + (\#\text{ vertices in }V_L\text{ with odd degree})\]We're excluding $u,v$ because their degree will now become even so walks can't start from $u,v$. Abbreviate "$\#\text{ vertices in }A\text{ with odd degree}$" with "$\# \ A\text{ odd}$". So, the number of good walks in G decreases by: \[\sum_{i=0}^{L-1} {(\# \ U_i\text{ odd})\cdot(\# \ V_{L-i-1}\text{ even}) + (\# \ U_i\text{ even})\cdot(\# \ V_{L-i-1}\text{ odd})} \]\[+ (\# \ U_L\text{ even} + \# \ V_L\text{ even}) - (\# \ U_L\text{ odd} + \# \ V_L\text{ odd})\]We need to show that this is even. Note that for every $1\leq i\leq L-1$, $(\# \ U_i\text{ odd})$ has the same parity as $|U_{i+1}|$. Let $|U_i|=x_i$ and $|V_i|=y_i$. We have, \[\sum_{i=0}^{L-1} (x_{i+1})(y_{L-i-1}-y_{L-i}) + (x_i-x_{i+1})(y_{L-i})\]\[ \equiv \sum_{i=1}^{L-1} x_{i+1}y_{L-i-1}-x_iy_{L-i} \pmod{2} \equiv x_L+y_L \pmod{2} \]\[\equiv (\# \ U_L\text{ even} + \# \ V_L\text{ even}) - (\# \ U_L\text{ odd} + \# \ V_L\text{ odd}) \pmod{2}\] So, the change in number of good walks is even and we're done with this case. A similar proof goes for the case with deg $u$, deg $v$ being both even. Case 2: deg $u$ is even and deg $v$ is odd. Continue the notations from the previous case. Then, for every $0\leq i\leq L-1$, the number of walks from $U_i$ to $V_{L-i-1}$ is, again: \[(\# \ U_i\text{ odd})\cdot(\# \ V_{L-i-1}\text{ even}) + (\# \ U_i\text{ even})\cdot(\# \ V_{L-i-1}\text{ odd})\] Again, we get \[\sum_{i=0}^{L-1}(\# \ U_i\text{ odd})\cdot(\# \ V_{L-i-1}\text{ even}) + (\# \ U_i\text{ even})\cdot(\# \ V_{L-i-1}\text{ odd}) \equiv x_L+y_L \pmod{2} \] There are $(\# \ U_L\text{ odd} + \# \ V_L\text{ even})$ good walks before and $(\# \ U_L\text{ even} + \# \ V_L\text{ odd})$ good walks after. Note, \[(\# \ U_L\text{ odd} \ + \ \# \ V_L\text{ even}) - (\# \ U_L\text{ even} \ + \ \# \ V_L\text{ odd}) \equiv x_L + y_L \pmod{2}\] Adding both gives that the change in number of good walks is even and we're done with this case as well. The proof is complete. $\blacksquare$