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 nertices with a vertex 2oloring c:V↦{0,1}uch that if deg(u)=deg(v)=1hen c(u)≠c(v)Let S:={e∈E∣es bichromatic }Then |S|s odd.
Proof. By the definition of a path graph, there exists a sequence ⟨vk⟩1<k≤nndexing V(G)An edge ek={vk,vk+1}s bichromatic iff c(vk)≠c(vk+1)A subgraph Hf Gs a state iff its terminal vertices are each incident with exactly one bichromatic edge or equal to a terminal vertex of GThe color of a state is the color of its vertices. There exists a subsequence of ⟨vk⟩ontaining the least term of each state; the index of a state is equal to the index of its least term in this subsequence.
Note that none of the states with even indexes are the same color as any of the states with odd indexes; hence all of the states with even indexes are the same color, and all of the states with odd indexes are the same color.
For each state Hthere exists a subsequence of ⟨vk⟩orresponding to the vertices of Hand the least term of each subsequence is either v1r some vkhat is the greatest term in a bichromatic edge. Thus the number of states in G=1+|S|
By contradiction, suppose that |S|s even. Then the number of states is odd, and the first and last states are the same color, so the terminal vertices of Gre the same color, contrary to our assumption that they are different colors. Thus |S|ust be odd.
Turning each node but the last blue from left to right conserves the parity of the bichromatic edge count at each step until it is still odd at the end.
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 nertices with a vertex 2oloring c:V↦{0,1}uch that if deg(u)=deg(v)=1hen c(u)≠c(v)Let S:={e∈E∣es bichromatic }Then |S|s odd.
Proof. By the definition of a path graph, there exists a sequence ⟨vk⟩1<k≤nndexing V(G)An edge ek={vk,vk+1}s bichromatic iff c(vk)≠c(vk+1)A subgraph Hf Gs a state iff its terminal vertices are each incident with exactly one bichromatic edge or equal to a terminal vertex of GThe color of a state is the color of its vertices. There exists a subsequence of ⟨vk⟩ontaining the least term of each state; the index of a state is equal to the index of its least term in this subsequence.
Note that none of the states with even indexes are the same color as any of the states with odd indexes; hence all of the states with even indexes are the same color, and all of the states with odd indexes are the same color.
For each state Hthere exists a subsequence of ⟨vk⟩orresponding to the vertices of Hand the least term of each subsequence is either v1r some vkhat is the greatest term in a bichromatic edge. Thus the number of states in G=1+|S|
By contradiction, suppose that |S|s even. Then the number of states is odd, and the first and last states are the same color, so the terminal vertices of Gre the same color, contrary to our assumption that they are different colors. Thus |S|ust be odd.
:::
Turning each node but the last blue from left to right conserves the parity of the bichromatic edge count at each step until it is still odd at the end.