Gram Stone

An attempt at problem #1; seems like there must be a shorter proof.

The proof idea is "If I flip a light switch an even number of times, then it must be in the same state that I found it in when I'm finished switching."

Theorem. Let $G=(V,E)$e a path graph on $n$ertices with a vertex $2$oloring $c:V\mapsto \{0,1\}$uch that if $deg\left(u\right)=deg\left(v\right)=1$hen $c\left(u\right)\ne c\left(v\right)$Let $S:=\{e\in E\mid e$s bichromatic $\}$Then $\left|S\right|$s odd.

Proof. By the definition of a path graph, there exists a sequence ${⟨v_k⟩}_{1<k\le n}$ndexing $V\left(G\right)$An edge $e_k=\{v_k,v_{k+1}\}$s bichromatic iff $c\left(v_k\right)\ne c\left(v_{k+1}\right)$A subgraph $H$f $G$s a state iff its terminal vertices are each incident with exactly one bichromatic edge or equal to a terminal vertex of $G$The color of a state... (read more)