Question

If \(G\) is a connected graph, a centre of \(G\) is a vertex \(v\) with the property that the maximum of the distances between \(v\) and the other vertices of \(G\) is as small as possible. By successively removing all the end-vertices, prove that every tree has either one centre or two adjacent centres. Give an example of a tree of each type with seven vertices.

Short answer

Every tree has either one centre or two adjacent centres. This is shown by successively removing end-vertices until only one or two vertices remain. Two seven-vertex examples are the chain and the star, adjusted to have two centres.

Step-by-step solution

Understand the concept of centre

A centre in a graph is a vertex that has the shortest maximum distance to all other vertices. In a tree graph, this is either one vertex or two adjacent vertices. The distance between vertices is measured in terms of the number of edges to cross to move from one vertex to another.

Construct the proof: Part 1

The proof is based on 'leaf removal' operation. Start by removing the 'leaves' (end-vertices) of the tree, then new leaves appear. Keep repeating this process. Since the given graph is a finite tree, repeating this process will eventually leave just one or two adjacent vertices.

Construct the proof: Part 2

These remaining vertices will have the smallest maximum distance to all other vertices in the tree, meaning they are the centres of the tree. If there is only one, it is a single centre. If there are two and they are adjacent, they are double adjacent centres.

Construct examples

For an example with a single centre, consider a chain of seven vertices (vertices 1-7) where each vertex is connected to the next (1-2, 2-3, 3-4, etc). The centre is vertex 4. For an example with two adjacent centres, consider a star-shaped tree of seven vertices where one vertex (vertex 1) is connected to all other vertices (2-7). Removing the leaves (vertices 2-7) leaves just vertex 1, which is a single centre vertex. However, if we connect vertex 2 to vertex 3 and make the remaining vertices (4-7) adjacent to either vertex 2 or 3, then 2 and 3 will be the two centres.

Key concepts

Graph Theory

Graph theory is a fundamental field within mathematics that studies the properties and structures of graphs—a set of points, called vertices, connected by lines, called edges. These edges can either be directed or undirected, creating a versatile framework for modeling relationships in various disciplines, from computer science and networking to biology and social sciences.

Understanding the nature of a graph involves exploring its various elements, such as paths, cycles, and, significantly for our discussion, centers. The center of a graph is not a mere geometrical term but a profound concept indicating the heart of activity or importance within the network. To visualize these concepts, consider a social network where vertices represent people, and edges represent friendships. The center of this network could be the person who, on average, is closest to everyone else within the group, known as the 'social butterfly'.

Graph theory is not just an abstract concept; it has practical applications in designing efficient networks, routing algorithms, understanding the spread of diseases, and much more. The beauty of graph theory lies in its ability to simplify complex systems into comprehensible visual models, providing tangible solutions to real-world problems.

Tree Graph

A tree graph, often simply called a 'tree', is a type of graph that is both connected and acyclic, meaning it has no cycles. Trees are a special subset of graphs where any two vertices are connected by exactly one simple path. In simpler terms, it's like a family tree or an organizational chart—there is a clear hierarchy and no way to loop back to the start once you move from one member to another.

The properties of a tree make it a fascinating study subject within graph theory. Due to its structure, a tree has a distinct number of edges — always precisely one less than the number of vertices. This trait implies profound implications for algorithms and computations since it simplifies many otherwise complex operations.

For instance, in computer science, tree data structures such as binary search trees and decision trees are employed in programming and data analysis for their efficiency in sorting and retrieving data. Trees are also fundamental in network design, illustrating how centers in a tree, ie. nodes with particular importance, can significantly impact the network's performance and resilience.

Leaf Removal

The leaf removal technique is a process used in graph theory to progressively simplify a tree until its basic structure, or center, is revealed. A 'leaf' in graph theory is a vertex with degree one—essentially a dead-end or terminal point of a path within a tree. Removing a leaf will not disrupt the connectivity of the tree, which makes this process a powerful tool for understanding a tree's structure.

This step-by-step process entails identifying and removing these leaf vertices, as well as their attached edges. Each leaf removal will, in turn, create new leaf vertices as the tree becomes smaller. Repeating this process in a finite tree will eventually result in one or two vertices remaining: these are the tree's centers. Whether there is one center or two depends on the tree's structure and balance.

By employing leaf removal, we can mathematically prove various properties of trees, such as the existence of tree centers. This method is not only theoretical but can be applied in practical situations like optimizing networks or analyzing organizational structures to find the most influential positions or roles.