$1.$In an undirected graph, the degree $d(u)$ of a vertex $u$ is the

number of neighbors $u$ has, or equivalently, the number of edges

incident upon it$.$ In a directed graph, we distinguish between the

in$-$degree $d_{in}(u),$ which is the number of edges into $u,$ and the

out$-$degree $d_{\text{o}\text{u}\text{t}}(u),$ the number of edges leaving $u.$

$($a$)$ Show that in an undirected graph, ${\displaystyle \underset{\text{u}\text{i}\text{n}\text{V}}{\overset{?}{}}}d(u)=2|E|.$

$($b$)$ Use part $($a$)$ to show that in an undirected graph, there must be

an even number of vertices whose degree is odd.

$($c$)$ Does a similar statement hold for the number of vertices with

odd in$-$degree in a directed graph?

$2.$Give a linear$-$time algorithm to determine whether an

undirected graph is bipartite.

$3.$An Eulerian tour in an undirected graph is a cycle that is

allowed to pass through each vertex multiple times, but must use each

edge exactly once. This simple concept was used by Euler in $1736$ to

solve the famous Konigsberg bridge problem, which launched the field

of graph theory.

$($a$)$ Show that an undirected graph has an Eulerian tour if and only

if all its vertices have even degree.

$($b$)$ An Eulerian path is a path which uses each edge exactly once.

Can you give a similar if$-$and$-$only$-$if characterization of which

undirected graphs have Eulerian paths?

$($c$)$ Can you give an analog of part $($a$)$ for directed graphs?