In an undirected graph, the degree d(u) of a vertex u is the number of neighbors

Question

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 din(u), which is the number of edges into u, and the out-degree dout(u), the number of edges leaving u. Show that in an undirected graaph, d(u) = 2|E|. Use part (a) to show that in an undirected graph, there must be an even number of vertices whose degree is odd. Does a similar statement hold for the number of vertices with odd in-degree in a directed graph?

Explanation / Answer

Part (a) For a vertex u, d(u) is the number of edges incident upon it. So sum of d(u) over V is the count of all edges incident on all the vertices. As an edge has exactly two vertices, all edges are counted exactly twice. So we have sum of d(u) over V = 2|E|. Part(b) Proof by contradiction. Suppose that there are an odd number of vertices with an odd degree. Then the sum of all degrees is odd. Yet, we proved in (a) that the sum of all degrees is even (as 2|E| must be an even number). This contradicts our assumption. So there must be an even number of vertices with an odd degree. Part (c) Proof by counterexample. This statement does not hold in a directed graph when considering indegrees. For example, in the 2 vertex simple graph (A ! B), we have din(A) = 0 and din(B) = 1. So, we have only 1 (odd) vertex with an odd degree. Cheers! Please rate :) :)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.