$($a$)$ On the axis from San Francisco traffic habits to Los Angeles traffic habits, Old California is more towards San Francisco: that is$,$ civilized. In Old California, all roads were one way streets. Suppose Old California had $n$ cities $)(2$ such that for every pair of cities $x$ and $Y,$ either $x$ had a road to $Y$ or $Y$ had a road to $x.$

Prove that there existed a city which was reachable from every other city by traveling through at most $2$ roads.

$[$Hint: Induction$]$

$($b$)$ Consider a connected graph $G$ with $n$ vertices which has exactly $2m$ vertices of odd degree, where $m>0.$ Prove that there are $m$ walks that together cover all the edges of $G($i$.$e$.,$ each