Understanding Undirected Graphs and Vertex Degrees

Let's analyze the given statements about undirected graphs. An undirected graph consists of a set of vertices (nodes) and a set of edges connecting pairs of vertices. In an undirected graph, the edges do not have a direction. The degree of a vertex is the number of edges incident to it.

Analyzing Statement I: Number of Odd Degree Vertices is Even

Statement I says that in any undirected graph, the number of vertices with an odd degree is always even. Let's consider the sum of the degrees of all vertices in the graph.

We know from the Handshaking Lemma (discussed in detail in Statement II) that the sum of the degrees of all vertices in an undirected graph is always equal to twice the number of edges. This means the sum of all degrees is always an even number.

Let $V$ be the set of vertices in the graph. We can split the set of vertices into two subsets: $V_{\text{odd}}$ containing vertices with odd degrees, and $V_{\text{even}}$ containing vertices with even degrees.

The sum of degrees can be written as:

$\sum_{v \in V} \text{deg}(v) = \sum_{v \in V_{\text{odd}}} \text{deg}(v) + \sum_{v \in V_{\text{even}}} \text{deg}(v)$

We know that $\sum_{v \in V} \text{deg}(v)$ is even (from Handshaking Lemma).

The sum of degrees of vertices in $V_{\text{even}}$ is a sum of even numbers, which is always an even number.

So, the equation becomes:

Even Number = $\sum_{v \in V_{\text{odd}}} \text{deg}(v) + \text{Even Number}$

For this equation to hold, $\sum_{v \in V_{\text{odd}}} \text{deg}(v)$ must also be an even number (Even - Even = Even).

The sum of degrees of vertices in $V_{\text{odd}}$ is the sum of several odd numbers. The only way the sum of odd numbers can be even is if there is an even count of those odd numbers.

For example:

• Sum of 1 odd number (e.g., 3) is odd.
• Sum of 2 odd numbers (e.g., 3 + 5) is even.
• Sum of 3 odd numbers (e.g., 3 + 5 + 7) is odd.
• Sum of 4 odd numbers (e.g., 3 + 5 + 7 + 9) is even.

Therefore, for the sum of degrees of odd-degree vertices ($\sum_{v \in V_{\text{odd}}} \text{deg}(v)$) to be even, the number of terms in the sum, which is the number of odd degree vertices ($|V_{\text{odd}}|), must be even.

Hence, Statement I is correct.

Analyzing Statement II: Sum of Degrees of all Vertices is Even

Statement II claims that the sum of the degrees of all vertices in an undirected graph is always an even number. This is a fundamental result in graph theory known as the Handshaking Lemma.

Consider an undirected graph $G = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges.

The degree of a vertex, $\text{deg}(v)$, is the number of edges incident to vertex $v$.

When we calculate the sum of degrees of all vertices ($\sum_{v \in V} \text{deg}(v)$), we are essentially counting how many times each edge is accounted for.

In an undirected graph, every edge connects exactly two distinct vertices. When we sum the degrees, each edge $(u, v) \in E$ contributes exactly 1 to the degree of vertex $u$ and exactly 1 to the degree of vertex $v$. Therefore, each edge $(u, v)$ is counted exactly twice in the total sum of degrees.

So, the sum of degrees of all vertices is equal to twice the number of edges in the graph. Let $|E|$ be the number of edges.

The Handshaking Lemma states:

$\sum_{v \in V} \text{deg}(v) = 2 \cdot |E|$

Since the sum of degrees is equal to $2 \times (\text{number of edges})$, and $2 \times (\text{any integer})$ is always an even number, the sum of degrees of all vertices in an undirected graph is always even.

Hence, Statement II is correct.

Conclusion on Undirected Graph Statements

Both Statement I (Number of odd degree vertices is even) and Statement II (Sum of degrees of all vertices is even) are correct properties of undirected graphs, derived from the fundamental Handshaking Lemma.

Revision Table: Properties of Undirected Graphs

Additional Information: Graph Theory Concepts

Graph theory is a branch of mathematics that studies graphs, which are mathematical structures used to model pairwise relations between objects. Key concepts include:

• Vertex (Node): A fundamental unit of which graphs are formed.
• Edge: A connection between two vertices. In an undirected graph, the connection is symmetric.
• Degree of a Vertex: The number of edges connected to a vertex. In a directed graph, we distinguish between in-degree and out-degree.
• Handshaking Lemma: A foundational theorem stating that the sum of degrees in an undirected graph is equal to twice the number of edges. This is because each edge contributes exactly two to the sum of degrees.
• Path: A sequence of vertices such that each adjacent pair in the sequence is connected by an edge.
• Cycle: A path that starts and ends at the same vertex.
• Connected Graph: A graph where there is a path between every pair of distinct vertices.