Elements of Graph Theory and Graph Models

Fundamental Definitions and Graph Representations

A graph $G = (V, E)$ is defined as a mathematical structure consisting of a finite set $V$ of vertices and a set $E$ of edges that join different pairs of distinct vertices. Within this framework, vertices are represented as points, and edges are represented as lines or curves joining the prescribed pairs of vertices. For example, a graph might be defined where the set of vertices is $V = \{a, b, c, d\}$ and the set of edges is $E = \{(a, b), (a, c), (a, d), (b, d), (c, d)\}$ . Each edge is essentially a pair of vertices, such as $(a, b)$ . It is important to note that the standard definition of a graph used in this context—often referred to in other texts as a "simple graph"—explicitly prohibits two edges from joining the same pair of vertices (no multiple edges) and disallows an edge from "looping" back to the same vertex (no self-loops). Consequently, every edge must have two distinct end vertices.

In an undirected graph, the order of the vertices in an edge pair does not matter; therefore, $(b, c)$ and $(c, b)$ denote the same edge. Two vertices, such as $a$ and $b$ , are said to be adjacent if there exists an edge $(a, b)$ connecting them. Conversely, directed graphs utilize ordered pairs of vertices known as directed edges. In these graphs, an edge $(b \rightarrow c)$ indicates a specific direction from vertex $b$ to vertex $c$ . Unlike undirected graphs, directed graphs allow for two edges between a pair of vertices, provided they are in opposite directions, such as $(a \rightarrow c)$ and $(c \rightarrow a)$ .

Combinatorial Reasoning and Methodology

Graph theory and enumeration require a different analytical approach compared to high school mathematics or calculus. There are few universal formulas; instead, most problems require a unique analysis involving the construction of clever models or creative thinking. A common strategy involves breaking a complex problem into multiple cases or subcases that can be solved using basic logic or counting rules. Another technique is to solve a specific special case and find a way to extend that reasoning to the general problem. As the problem-solver George Polya famously stated: "The challenging part is asking the right questions. Then the answers are easy."

Graphs facilitate these combinatorial arguments by providing a visual depiction. Drawing a graph makes case-by-case arguments much easier to construct. Graphs are versatile tools for any scenario involving a set of elements related by a specific property. Physical examples include electrical networks (transistors as vertices, wires as edges), telephone systems (telephones/switch centers as vertices, lines as edges), road maps, oil pipelines, and subway systems. Logical or hierarchical examples include computer flowcharts (instructions as vertices, logical flow as edges), organizational charts (people as vertices, superior-subordinate relationships as edges), computer data structures, evolutionary trees in biology, and task scheduling.

Paths, Circuits, and Connectedness

To analyze the structure of graphs, several key terms are defined. A path $P$ is a sequence of distinct vertices, denoted $P = x_1-x_2- \dots -x_n$ , where every pair of consecutive vertices in the sequence is joined by an edge. If, in addition to this path, there is an edge joining the first and last vertices $(x_n, x_1)$ , the sequence is called a circuit, written $x_1-x_2- \dots -x_n-x_1$ . For instance, in a graph with vertices $\{a, b, c, d\}$ , the sequence $b-d-a-c$ might form a path, while $a-b-d-c-a$ would constitute a circuit.

A graph is described as connected if a path exists between every possible pair of vertices. If the removal of specific edges or vertices results in a graph where at least one pair of vertices is no longer joined by a path, the graph is said to be disconnected. A vertex's degree is defined as the number of edges incident to that vertex.

Graph Models: Matching and Bipartite Graphs

In the matching problem (Example 1), we consider a set of five people $\{A, B, C, D, E\}$ and five jobs $\{a, b, c, d, e\}$ . The goal is to determine if a one-to-one matching exists such that each person is assigned a job for which they are qualified. This is modeled by a graph where vertices represent people and jobs, and edges connect individuals to their qualified tasks. If a subset of people (e.g., $A, B, D$ ) is collectively qualified for fewer jobs (e.g., only $c, d$ ) than there are people in that subset, a feasible matching for the entire group is impossible.

Graphs where edges only connect vertices between two distinct sets (like people and jobs) without any edges connecting vertices within the same set are called bipartite graphs. These are characterized by the fact that internal sets of vertices have no horizontal edges connecting them.

Graph Models: Trees and Search Procedures

Example 2 illustrates the use of trees in search algorithms, such as a computer spelling checker. To find a match for a word $X$ among 100,000 dictionary entries, the computer uses a tree of comparisons. For a single letter, it might first compare $X$ to $M$ . If $X \leq M$ , the search narrows to the first 13 letters; if X > M, it moves to the last 13. This process of "cutting the search in half" continues until the target is found. A directed graph representing these choices is called a tree. In just 12 rounds of comparisons, a computer can reduce 100,000 possibilities to approximately 25, which can then be searched linearly. Formally, a tree is a connected graph that has a unique path between any pair of vertices (ignoring edge directions).

Trees also appear in network reliability (Example 3). In a telephone network, we may seek a minimal connecting set of edges to link $n$ vertices. A minimal connecting set for a graph with $n$ vertices will always be a tree and will always contain exactly $n-1$ edges. This set ensures connectivity with the fewest possible links.

Graph Models: Coverage and Independence

Surveillance problems (Example 4) often involve finding an edge cover. An edge cover is a set of vertices $C$ such that every edge in the graph is incident to at least one vertex in $C$ . In a city street map with 14 blocks (edges), if we want to minimize the number of police officers at corners (vertices) to watch every block, we seek a minimal edge cover. The analysis uses the AC Principle (Assumptions generate helpful Consequences). For example, if we assume an edge $(x, y)$ connects a degree-3 vertex $x$ and a degree-2 vertex $y$ , we may deduce that at most one of those vertices can be used in a minimal five-vertex cover. Following these logical consequences helps identify the exact vertices required to solve the problem or prove a contradiction.

Scheduling problems (Example 5) often involve independent sets. An independent set is a group of vertices where no two vertices are joined by an edge. In a legislative context, committees that have overlapping members cannot meet at the same hour. If committees are vertices and overlaps are edges, then a set of committees that can meet simultaneously constitutes an independent set. There is a fundamental relationship between these concepts: for a set of vertices $V$ , a subset $I$ is an independent set if and only if its complement $V - I$ is an edge cover. Consequently, finding a maximal independent set is equivalent to finding a minimal edge cover.

Influence Models and Vertex Bases

Directed graphs can model influence (Example 6). If person $p_1$ influences person $p_2$ , a directed edge $(p_1 \rightarrow p_2)$ is drawn. A vertex basis is a minimal subset of vertices from which directed paths exist to all other vertices in the graph. This concept helps identify the smallest group of people needed to spread an idea to everyone else. A directed-path graph can be constructed to simplify this task: the vertex set remains the same, but an edge $(p_i \rightarrow p_j)$ is created if there is any directed path from $p_i$ to $p_j$ in the original graph. Vertices with no incoming edges in this path graph must be included in the vertex basis.

Graph Isomorphism

Isomorphism addresses whether two graphs are structurally identical despite being drawn differently or having different vertex names. Two graphs $G$ and $G'$ are isomorphic if there is a one-to-one correspondence between their vertices such that adjacency is preserved. If vertex $u$ matches $u'$ and $v$ matches $v'$ , then $u$ is adjacent to $v$ in $G$ if and only if $u'$ is adjacent to $v'$ in $G'$ .

Key properties (invariants) preserved under isomorphism include:

The same number of vertices.
The same number of edges.
The same degrees for matched vertices.
The same number of vertices of any given degree.
Isomorphic subgraphs (e.g., if $G$ has a chordless circuit of length 6, $G'$ must also have one).

A complete graph on $n$ vertices, denoted $K_n$ , is a graph where every vertex is adjacent to every other vertex. Every graph on $n$ vertices is a subgraph of $K_n$ . Determining isomorphism is practically significant in fields like organic chemistry (identifying known compounds by molecular structure) and integrated circuit design (reusing isomorphic circuit solutions).

Symmetry, Complements, and Directed Isomorphism

In symmetric graphs (Example 2), the AC Principle helps construct an isomorphism by matching a vertex (e.g., $a$ matches $1$ ) and then matching its neighbors according to their own subgraph structures. If the construction leads to a contradiction, the graphs are not isomorphic. Another tool is the complement graph $\overline{G}$ , which possesses the same vertices as $G$ but contains edges only between pairs of vertices that are not connected in $G$ . Graphs $G_1$ and $G_2$ are isomorphic if and only if their complements $\overline{G}_1$ and $\overline{G}_2$ are isomorphic.

For directed graphs (Example 3), isomorphism requires matching in-degrees (edges pointing in) and out-degrees (edges pointing out), as well as directed path structures. For instance, if one graph contains a directed circuit that visits all vertices and another does not, they cannot be isomorphic.

Universal Principles of Edge Counting

Graphs are governed by Theorem 1, often called the Handshaking Lemma: In any graph, the sum of the degrees of all vertices is equal to twice the number of edges ( $\sum_{v \in V} \text{deg}(v) = 2|E|$ ). This occurs because every edge is incident with exactly two vertices, contributing two to the total degree sum. A direct Corollary is that in any graph, the number of vertices of odd degree must be even.

This theorem permits several useful calculations:

If a graph has 20 edges and every vertex has degree 4, the number of vertices $v$ is found by $4v = 2 \times 20$ , resulting in $v = 10$ .
For a complete graph $K_n$ , each vertex has degree $n-1$ . The sum of degrees is $n(n-1)$ , so the number of edges is $\frac{n(n-1)}{2}$ .
It is impossible to have a group of seven people where each knows exactly three others, as this would require 7 vertices of degree 3, violating the corollary that the number of odd-degree vertices must be even.

The Mountain Climbers Puzzle

The Mountain Climbers Puzzle (Example 4) demonstrates the application of the Handshaking Lemma's corollary. Two climbers at the same elevation on opposite sides of a peak $M$ want to move such that they remain at the same altitude at all times. This is modeled by a "range graph" where vertices are pairs of points $(P_L, P_R)$ at equal altitudes. Starting and summit vertices have degree 1, while most other vertices have degree 2 or 4. Since the start vertex $(A, Z)$ and summit $(M, M)$ are the unique vertices of odd degree, they must belong to the same connected component (otherwise, a component would have only one odd-degree vertex, which is impossible). Thus, a path between them must exist.

Bipartite Graphs and Circuit Length

Theorem 2 states that a graph $G$ is bipartite if and only if every circuit in $G$ has even length. To prove this, note that in a bipartite graph, any circuit must alternate between the two sets of vertices, requiring an even number of steps to return to the start. Conversely, if all circuits are even, we can partition the graph by placing vertex $a$ on the left and any vertex at an odd distance from $a$ on the right, while vertices at an even distance from $a$ are placed on the left. This construction fails only if an odd-length circuit exists. This theorem provides a systematic way to test if a graph is bipartite by attempting to arrange its vertices into two sets according to path parity.