How to write a proper, rigorous proof: Colouring vertices on a line graph

Question

I would like to practice proof-writing as I am afraid of lacking the mathematical rigor needed to be perfectly clear and precise.

Therefore I would be very glad, if someone could verify my solution to the following problem and maybe point out, if something could be improved.

Problem: Given be a linear graph whose vertices are coloured either green or blue such that the first and the last vertix are coloured differently.

Now one counts the number $m$ of edges connecting two differently coloured vertices.

To prove: This number is odd.

My solution:

Assume there is a shortest graph of $n \ge 2 $ vertices $v_1, \dots v_n$ so that there is an even number of edges connecting two differently coloured vertices. As the first and the last node are coloured differently, one has $n\ge 3$ and $m \ge 2$

Wlog, $v_1$ is green and $v_n$ is blue. Now we choose the node vertix $v_r$ such that all nodes $v_l$ with $l \gt r$ are blue. We are then counting the number of differently coloured edges $a$ between $v_1$ and $v_r$, edges $b$ between $v_{r+1}$ and $v_n$ respectively.

$a$ and $b$ can't be either even and odd or odd and even:

Case 1. $a$ even, $b$ odd

If $a \gt 0$, then the base assumption is violated that the current graph is the shortest with the desired property. Thus: $r=1$

As $v_{r+1}$ is blue and $b$ odd, there has to be at least one green vertix $v_k$ such that $r \lt k \lt n$. This is however also not possible by the definition of $v_r$. Thus $a$ cannot be even, $b$ odd.

Case 2: $a$ odd and $b$.

This case can be handled in similar fashion, which concludes the proof.

My thoughts: This proof feels tedious. In particular because the problem is fairly simple borderline of being obvious. However I still found it hard to actually write it down due to some details. Thus the question: Can above proof be improved?

Answer 1

I think a simpler way to prove it by induction is to prove the stronger statement that the number is odd if and only if the first and last vertex are different colours. Then you can just take off the last vertex.

Alternatively, prove it directly: adding an extra edge to complete a cycle, argue that the number of edges from blue to green equals the number from green to blue. So the cycle has an even number, meaning the path had an odd number.

Answer 2

Take a step back.

Somebody [citation needed] said that to understand a proof, you have to read through it and check what it proves. Sounds awfully circular, I know. But the gist is that the proof is meant to be read (and understood) by people. As such, "maximal formality and rigour" is often an obstacle to reading and understanding.

Check example proofs from your textbooks (they'll be more detailed and wordy than the ones flung around by professionals!), they should give you a guide on how far to push formality. Look for alternative proofs, ones that are more intuitive, shorter, use simpler machinery.

Flip through Aigner's "Proofs from THE BOOK". Erdös (himself an atheist) said god maintained a book with the best proofs of all mathematics, this text (which Erdös himself added to enthusiastically until his death) aims at collecting beautiful proofs from all areas accessible to an amatheur.