Graph Theory: Basic Concepts, Definitions, and the Handshaking Theorem

Learn the fundamental concepts of graph theory, including definitions of graphs, vertices, edges, and the degree of a vertex. This guide also presents and proves the Handshaking Theorem, a key result relating vertex degrees and the number of edges in a graph.

Graph Theory: Basic Concepts and Definitions

Understanding Graphs

A graph G is a structure consisting of two sets: a set V of vertices (also called nodes or points) and a set E of edges (lines connecting pairs of vertices). We often write this as G = (V, E).

Degree of a Vertex

The degree of a vertex is the number of edges connected to it. A self-loop (an edge connecting a vertex to itself) contributes 2 to the degree.

Examples: Calculating Vertex Degrees

(Two examples illustrating how to calculate the degree of each vertex in a graph are given in the original text and should be included here. The solution showing the degree of each vertex should be included.)

Handshaking Theorem

(The statement and proof of the Handshaking Theorem—that the sum of the degrees of all vertices in a graph is twice the number of edges—are given in the original text and should be included here.)

Paths and Circuits

  • Path: A sequence of vertices and edges where no vertex or edge is repeated. A path is open (starts and ends at different vertices). The length of a path is the number of edges.
  • Simple Path: A path with no repeated edges.
  • Elementary Path: A path with no repeated vertices.
  • Circuit (Closed Path): A path that starts and ends at the same vertex.
  • Simple Circuit: A circuit with no repeated edges (except the start and end vertex).

Example: Paths and Circuits

(An example graph is provided in the original text, along with questions about identifying simple paths, elementary paths, simple paths that are not elementary, paths that are not simple, simple circuits, and circuits that are not simple. The solutions for all of these should be included here.)

Additional Graph Terminology

  • Pendant Vertex: A vertex with degree 1.
  • Pendant Edge: An edge connected to a pendant vertex.
  • Odd Vertex: A vertex with an odd degree.
  • Even Vertex: A vertex with an even degree.
  • Incident Edge: An edge connected to a vertex.
  • Adjacent Vertices: Two vertices connected by an edge.
  • Self-loop: An edge connecting a vertex to itself.
  • Isolated Vertex: A vertex with degree 0.

Example: Identifying Graph Features

(An example graph is given in the original text, along with questions asking to identify pendant vertices, pendant edges, odd vertices, even vertices, incident edges, and adjacent vertices. The solutions to all of these are given in the original text and should be included here.)

Cut Sets and Cut Vertices (Cut Points)

  • Cut Set: A minimal set of edges whose removal disconnects the graph.
  • Cut Vertex (Cut Point): A vertex whose removal increases the number of connected components.

(An example demonstrating cut sets and a graph showing how the removal of a vertex changes the connectivity is provided in the original text and should be included here.)

Bridges (Cut Edges)

A bridge is an edge whose removal increases the number of connected components.

(An example demonstrating bridges and the change in connectivity when a bridge is removed is given in the original text and should be included here.)

Conclusion

These fundamental concepts and definitions form the building blocks of graph theory, providing a vocabulary and framework for analyzing and understanding the structure and properties of graphs.