Question

In an undirected graph, the $\mathit{d}\mathit{e}\mathit{g}\mathit{r}\mathit{e}\mathit{e}\mathbf{\hspace{0.33em}}\mathit{d}\mathbf{\left(}\mathit{u}\mathbf{\right)}$ of a vertex u is the number of neighbours 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 $\mathbf{indegree}\mathbf{\hspace{0.33em}}{\mathbf{d}}_{\mathbf{in}}\mathbf{\left(}\mathbf{u}\mathbf{\right)}$, which is the number of edges into u, and the $\mathit{o}\mathit{u}\mathit{t}\mathit{d}\mathit{e}\mathit{g}\mathit{r}\mathit{e}\mathit{e}\mathbf{\hspace{0.33em}}{\mathit{d}}_{\mathbf{o}\mathbf{u}\mathbf{t}}\mathbf{\left(}\mathit{u}\mathbf{\right)}$, the number of the edges leaving u.

(a) Show that in an undirected graph, role="math" localid="1658908755010" $\mathbf{\sum }_{\mathbf{uev}}\mathbf{}\mathbf{d}\mathbf{\left(}\mathbf{u}\mathbf{\right)}\mathbf{=}\mathbf{2}\mathbf{\left|}\mathbf{E}\mathbf{\right|}$

(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 indegree in a directed graph?

Short answer

(a) It can be proved that in an undirected graph,$\sum _{\mathrm{uev}}\mathrm{d}\left(\mathrm{u}\right)=2\left|\mathrm{E}\right|$.

(b) Using part (a). it has been shown that in an undirected graph, there must be an even number of vertices whose degree is odd.

(c) No, a similar statement does not hold for the number of vertices with odd indegree in a directed graph.

Step-by-step solution

Explain the undirected graph and the degree

Consider the graph, that has edges without arrows that point in no direction. The degree is the number that represents the number of incoming edges of the

Show that in an undirected graph,∑uev d(u)=2|E|

(a)

For any edge (u,v), it contributes a degree to vertexu and vertexv at the same time. So, the edges correspond to two degrees, so the degree of the vertices is as follows.

$\sum _{uev}\mathrm{d}\left(\mathrm{u}\right)=2\left|\mathrm{E}\right|$

Therefore, it is shown that in an undirected graph,$\sum _{uev}\mathrm{d}\left(\mathrm{u}\right)=2\left|\mathrm{E}\right|$.

Show that in an undirected graph,∑uev d(u)=2|E|

(b)

The sum of the edges of the each vertex is an even number, it can be seen that the number of vertices with an odd degree must be an even number.

Consider the solution of the part(a),$\sum _{uev}\mathrm{d}\left(\mathrm{u}\right)=2\left|\mathrm{E}\right|$,that shows that the sum of the vertices equal the even number of edges.

Therefore, Using part (a). it has been shown that in an undirected graph, there must be an even number of vertices whose degree is odd.

Show that in an undirected graph,∑uev d(u)=2|E|  

(c)

Consider the directed graph that has the indegrees $d_{in}$and outdegrees $d_{out}$. The indegree represents the number of incoming edges and the out degree represents the number of the outgoing edges from the vertex.

In the directed graph,

role="math" localid="1658912427821" $\sum _{uev}\mathrm{d}\left(\mathrm{u}\right)+{\mathrm{d}}_{\mathrm{out}}=2\left|\mathrm{E}\right|$, but the parity of the sum of indegrees cannot be determined.

Therefore a similar statement does not hold for the number of vertices with odd indegree in a directed graph.