Graph Measurements in Discrete Mathematics: Quantifying Graph Properties

Explore key measurements used to quantify properties of graphs in discrete mathematics. This guide defines and illustrates various graph measurements, including length, degree of a vertex, and path length, providing examples and calculations.

Graph Measurements in Discrete Mathematics

Understanding Graphs

A graph is a collection of points (called vertices or nodes) connected by lines (called edges). Graphs are used to represent relationships between objects. We often represent a graph as G = (V, E), where V is the set of vertices, and E is the set of edges.

Example Graph

(An illustrative graph with vertices {1, 2, 3, 4, 5, 6} and the specified edges should be included here.)

Graph Measurements

1. Length of a Graph

The length of a graph is simply the total number of edges in the graph.

(For the example graph, the length is 8.)

2. Distance Between Two Vertices

The distance between two vertices is the number of edges in the shortest path connecting them. If multiple shortest paths exist, we consider any of the shortest paths.

(Examples calculating the distances between specific vertices in the example graph are provided in the original text and should be included here.)

3. Eccentricity of a Vertex

The eccentricity of a vertex is the greatest distance between that vertex and any other vertex in the graph. It's a measure of how "far" a vertex is from the furthest vertex it's connected to.

(An example calculating the eccentricity of a vertex in the example graph is provided in the original text and should be included here.)

4. Diameter of a Graph

The diameter of a graph is the largest eccentricity among all vertices in the graph. It represents the longest shortest path between any two vertices in the graph.

(For the example graph, the diameter is 3.)

5. Radius of a Graph

The radius of a graph is the smallest eccentricity among all vertices in the graph. It represents the smallest maximum distance from a central point in the graph to all other vertices.

(For the example graph, the radius is 2.)

6. Center of a Graph

The center of a graph consists of all vertices whose eccentricity equals the graph's radius. These vertices are considered the "central" points of the graph.

(For the example graph, the center is vertex 4.)

7. Circumference of a Graph

The circumference of a graph is the length (number of edges) of the longest cycle (a closed path with no repeated vertices except the start and end vertex) in the graph.

(For the example graph, the circumference is 6.)

8. Girth of a Graph

The girth of a graph is the length (number of edges) of the shortest cycle in the graph.

(For the example graph, the girth is 4.)

Conclusion

These measurements provide quantitative ways to describe the structure and properties of graphs, which is fundamental in graph theory and its applications.