Question

Let \(T\) be a tree. Prove that if an edge \(e\) joins two nonadjacent vertices in \(T,\) then \(T \cup\) [e\\} contains a cycle.

Short answer

Adding an edge between two nonadjacent vertices in a tree forms a cycle.

Step-by-step solution

Understanding the Problem

We need to show that by adding an edge \( e \) between two nonadjacent vertices of a tree \( T \), the resulting graph \( T \cup \{ e \} \) will form a cycle.

Recall Tree Properties

A fundamental property of trees is that they are connected graphs with no cycles and \( n-1 \) edges for \( n \) vertices. Any additional edge will create a cycle.

Define the Nonadjacent Vertices

The problem specifies adding an edge \( e \) between two nonadjacent vertices. In a tree, nonadjacent vertices are those that are not directly connected by an edge.

Constructing the Path

Identify the unique path \( P \) within \( T \) that connects the two vertices \( u \) and \( v \). This path exists because \( T \) is connected.

Adding the Edge e

Add the edge \( e \) that directly connects \( u \) and \( v \). Now the new edge \( e \) alongside the path \( P \) forms a cycle, as the cycle is \( P \cup \{ e \} \).

Conclude the Proof

Since adding \( e \) creates a cycle, the graph \( T \cup \{ e \} \) is no longer a tree. This proves our assertion that connecting two nonadjacent vertices in a tree results in a cycle.

Key concepts

Graph Cycle

In graph theory, a cycle is a path that starts and ends at the same vertex without retracing any edge. Imagine a simple closed loop, like a circle in a network. Cycles are not typical in tree structures because they consist of unique paths.
Trees by definition are acyclic, meaning they contain no cycles. When you add an edge between two nonadjacent vertices in a tree, you essentially create a pathway that closes into a cycle.
This is because the added edge completes a route that can return to the starting point, completing a loop. It’s like connecting two points of a path that already has a unique route, thus forming a full circle.

Tree Properties

Trees are special types of graphs characterized by their set of properties. Firstly, they are connected, meaning there is a unique path between any two vertices. This connectivity ensures there are no multiple ways to traverse between two nodes without a backtrack.
Another critical property is the absence of cycles, which is why they appear as branches without any closed loops, hence the name 'tree'. If you add an edge that connects two previously nonadjacent vertices, it inevitably forms a cycle since it introduces an alternative shorter path between them.
Moreover, for a tree with \( n \) vertices, the number of edges is \( n-1 \). Adding an edge disrupts this balance, further indicating the formation of a cycle.

Graph Connectivity

Graph connectivity refers to how well connected the vertices are within a graph. In a tree, connectivity is ensured by a single, unique path between any pair of vertices, ensuring they are always reachable from each other. This also means each pair is only connected once and uniquely, defining the tree structure.
When you add an edge in a tree between two nonadjacent vertices, the connectivity changes. It introduces a new pathway, forming a redundant connection that results in a cycle. This additional connection is what stops the graph from being a tree anymore, because it connects vertices in a way that violates the unique pathway rule of trees.
Thus, graph connectivity in context of trees involves preserving the single path nature between vertices, and any deviation from this results in changes such as cycle formation.