(Solved): 1.In an undirected graph, the degree d(u) of a vertex u is the number of neighbors u has, or equival ...
1.In an undirected graph, the degree
d(u)of a vertex
uis the number of neighbors
uhas, 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_(out )(u), the number of edges leaving
u. (a) Show that in an undirected graph,
\sum_(uinV) 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?
