Problem 13 - Discrete Mathematics with Applications

Question

Let \(T\) be a tree with vertices \(v_{1}, \ldots, v_{n} .\) Show that \(\sum_{i=1}^{n} \operatorname{deg}\left(v_{i}\right)=2 n-2\)

Step-by-Step Solution

Answer

By applying the Handshaking Lemma and the tree theorem, we find that the sum of the degrees of all vertices of a tree T with vertices \(v_1, \ldots, v_n\) is equal to twice the total number of edges in the graph, which is \(2(n-1)\). Simplifying this expression, we obtain the desired result: \(\sum_{i=1}^{n} \operatorname{deg}(v_i) = 2n-2\).

Step 1: Recalling the Handshaking Lemma

Recall the Handshaking Lemma, one of the basic graph theory concepts, which states that the sum of the degrees of all the vertices of a graph is equal to twice the total number of edges in the graph. This can be written as: \[\sum_{i=1}^{n} \operatorname{deg}(v_i) = 2 |E|\] where \(|E|\) represents the total number of edges in the graph.

Step 2: Applying the Tree Theorem

From the given exercise, T is a tree with vertices \(v_1, \ldots, v_n\). According to the tree theorem, a tree of n vertices has n-1 edges. Therefore, in the tree T, the total number of edges |E| is equal to \(n-1\), i.e., |E| = n-1.

Step 3: Substituting the value of |E| in the Handshaking Lemma

Now that we have the total number of edges |E| = n-1, we can substitute this value into the Handshaking Lemma equation. This gives the following equation: \[\sum_{i=1}^{n} \operatorname{deg}(v_i) = 2 (n-1)\]

Step 4: Simplifying and obtaining the final result

Finally, by simplifying the above equation, we get the desired result: \[\sum_{i=1}^{n} \operatorname{deg}(v_i) = 2n-2\] Thus, the sum of the degrees of all vertices of a tree T with vertices \(v_1, \ldots, v_n\) is equal to \(2n-2\).

Key Concepts

Handshaking Lemma

The Handshaking Lemma is a foundational concept in graph theory. It asserts that, in any graph, the sum of the degrees of all vertices equals twice the number of edges. But why is this true? Imagine a group of people shaking hands. Each handshake involves two people, so counting all handshakes twice (once for each participant) gives us double the number of handshakes. Similarly, in a graph, each edge connects two vertices, contributing a degree of 1 to each vertex it connects. Thus, each edge is counted twice when summing up vertex degrees.

This leads us to the formal expression:

• For any graph, \( \sum_{i=1}^{n} \text{deg}(v_i) = 2|E| \), where |E| is the number of edges.

Breaking this down:

• The degree of a vertex, \( \text{deg}(v_i) \), represents the number of edges connected to it.
• The summation across all vertices counts each edge twice.

Hence, this lemma provides significant insight into the relationship between vertices and edges in graphs.

Tree Theorem

The Tree Theorem is specific to trees in graph theory. A tree is a connected, acyclic graph, which means it has no cycles and is composed of connected vertices. A fundamental characteristic of trees is that they have exactly \( n-1 \) edges if they consist of \( n \) vertices.

Why \( n-1 \) edges? The reasoning involves two main aspects:

• Connectivity: every vertex must be reachable from every other vertex, ensuring there is a path linking all vertices.
• Acyclic nature: since a tree cannot have cycles, adding more than \( n-1 \) edges would inevitably create a cycle.

Combining these properties, you can think of building a tree by starting with a single vertex and progressively adding vertices linked by edges, one at a time, reaching \( n-1 \) edges for \( n \) vertices. This explains why

• a tree with \( n \) vertices consists of \( n-1 \) edges.

This property becomes crucial when applying the Handshaking Lemma to trees, as it allows for the correct calculation of the sum of vertex degrees.

Vertex Degree

Vertex degree is a fundamental concept in understanding graph structures. The degree of a vertex, often denoted as \( \text{deg}(v) \), is the count of how many edges are linked to that vertex. This concept provides a measure of connectivity of a vertex within the graph.

Key points about vertex degree include:

• A vertex with a high degree is connected to many other vertices, signifying it as a kind of 'hub' in the graph.
• Degrees are integral in understanding graph properties, such as finding cut points or determining network centrality.

In the context of trees, vertex degrees are particularly insightful. With the Handshaking Lemma and Tree Theorem in hand,

• the sum of degrees becomes succinctly computed: \( 2(n-1) = 2n-2 \), using the fact that a tree has \( n-1 \) edges.

This relationship underscores the interaction between each vertex's connectivity and the overall tree structure. Understanding vertex degrees is essential for analyzing and interpreting graphs, especially when assessing network robustness or identifying critical nodes.