Special Graphs, Planarity, and Theorems

Graph theory provides the formal mathematical language to describe networks, structures, and relationships across computer science and discrete mathematics. This document explores the structural classifications of graphs, algebraic representations, trees, and the fundamental topological theorems governing planarity.

1. Basic Graph Definitions and Structural Properties

A graph $G$ is formally defined as an ordered pair $G = (V, E)$ , where $V$ is a non-empty set of vertices (or nodes) and $E$ is a set of edges. A mapping function $\phi$ associates each edge in $E$ with a pair of vertices from $V$ .

Vertices ( $V$ ): The fundamental, distinct points or entities in the graph.
Edges ( $E$ ): The structural linkages connecting pairs of vertices.
Adjacent Nodes: Two vertices $u, v \in V$ are adjacent if there exists an edge $e \in E$ that connects them.
Directed Edge: An ordered pair of vertices $(u, v)$ representing a one-way path originating at (the ) and terminating at (the ).

Based on these edge characteristics, we distinguish major graph classes:

text

       Simple Graph                      Multigraph
        (No loops)                (Parallel edges, loop)
 
          A ---- B                         A ===== B
          |    /                           |     / \
          |   /                            |    /   ) e3
          |  /                             |   /   /
          C                                C--O (Loop)

Digraph (Directed Graph): A graph where every edge is directed.
Undirected Graph: A graph where every edge is undirected.
Incident: An edge is incident to the vertices it connects.
Loop (Sling): An edge that originates and terminates at the same vertex (i.e., $(v, v)$ ).
Parallel Edges: Two or more distinct edges that connect the same pair of vertices.
Multigraph: A graph that permits parallel edges.
Simple Graph: A graph containing no loops and no parallel edges. In a directed simple graph, there is at most one directed edge from $u$ to $v$ .
Weighted Graph: A graph where each edge $e \in E$ is assigned a numerical value or "weight" , representing costs, distances, or capacities.

2. Node Degrees, Subgraphs, and Isomorphism

Node Degrees

In directed graphs, we partition the degree of a node based on edge orientation:

Outdegree ( $\text{deg}^+(v)$ ): The number of directed edges originating from $v$ .
Indegree ( $\text{deg}^-(v)$ ): The number of directed edges terminating at $v$ .
Total Degree (): The sum of the indegree and outdegree:

Subgraphs and Digraph Relations

A graph $H = (V_H, E_H)$ is a subgraph of $G = (V_G, E_G)$ (denoted ) if and . If , then is a .

For simple digraphs, we can interpret edges as binary relations over the set of vertices $V$ . These relations can satisfy classic set-theoretic properties:

Reflexive: Every node contains a loop ( $\forall v \in V, (v, v) \in E$ ).
Symmetric: For any edge $(u, v) \in E$ , the reversed edge $(v, u) \in E$ also exists.

The converse (or dual/reversal) of a digraph $G$ , denoted $G^T$ , is obtained by reversing the direction of every edge in $E$ .

Graph Isomorphism

Two graphs $G = (V_G, E_G)$ and $H = (V_H, E_H)$ are () if there exists a bijective function such that for any :

A graph invariant is a property of a graph that remains unchanged under isomorphism. Examples of invariants include:

The number of vertices ( $|V|$ ).
The number of edges ( $|E|$ ).
The degree sequence (the sorted list of degrees of the vertices).

3. Connectivity, Reachability, and Node Bases

Reachability and Node Bases

The reachable set $R(v)$ of a node $v$ in a digraph is the set of all vertices $u \in V$ such that there exists a directed path from $v$ to $u$ .

A node base $S \subseteq V$ is a minimal subset of vertices from which every vertex in the graph is reachable. It satisfies three core criteria:

Every vertex $v \in V$ is reachable from at least one vertex in $S$ .
$S$ must contain all isolated nodes and all nodes with an indegree of zero ( $\text{deg}^-(v) = 0$ ).
No vertex is reachable from any other vertex .

Connectivity

We classify graph connectivity based on the existence of paths:

text

  Strongly Connected                Weakly Connected
     (Bidirectional)             (Connected if undirected)
 
      A <=======> B                    A --------> B
      |           ^                    ^           ^
      |           |                    |           |
      v           |                    |           |
      C --------> D                    C --------> D

Undirected Connected Graph: An undirected graph where a path exists between every pair of distinct vertices.
Weakly Connected Digraph: A digraph that is connected when all edge directions are ignored (treated as an undirected graph).
Unilaterally Connected Digraph: A digraph where, for any pair of vertices $u$ and $v$ , there is a directed path from $u$ to $v$ or from $v$ to $u$ .
Strongly Connected Digraph: A digraph where, for any pair of vertices $u$ and , there is a directed path from to from to .

Structural Vulnerability

Cut Vertex (Articulation Point): A vertex whose removal (along with its incident edges) increases the number of connected components in the graph.
Cut Edge (Bridge): An edge whose removal increases the number of connected components.

text

                  Bridge
          A --- B ====== C --- D
          |   /          |   /
          |  /           |  /
          E              F
       Sub-component 1   Sub-component 2

4. Matrix Representations of Graphs

Graphs can be modeled algebraically using matrices, enabling efficient computational operations.

Adjacency Matrix

For a graph $G$ with $n$ vertices ordered $v_1, v_2, \dots, v_n$ , the is an Boolean or integer matrix where:

Properties of the adjacency matrix:

For an undirected graph, $A$ is symmetric ( $A = A^T$ ).
The sum of elements in row $i$ equals the outdegree of $v_i$ : $_{}^{}$ .

Path Counts and the Path Matrix

To find the number of paths of length $k$ between vertices, we use matrix multiplication. The element in row $i$ , column $j$ of the matrix $A^k$ represents the exact number of paths of length $k$ from $v_i$ to .

The path matrix (or reachability matrix) $P$ is an $n \times n$ Boolean matrix where $p_{ij} = 1$ if there is a path of any length from $v_i$ to , and otherwise. It is computed via the Boolean join of powers of : Alternatively, we can define the path count sum matrix as:

Incidence Matrix

For an undirected graph with $V$ vertices and $E$ edges, the incidence matrix $M$ is a $V \times E$ matrix where: $m_{ij} = \begin{cases} 1 & \text{if vertex } v_i \text{ is incident to edge } e_j \\ 0 & \text{otherwise} \end{cases}$

Architectural Trade-offs

Adjacency List: Highly efficient for sparse graphs ( $|E| \ll |V|^2$ ), optimizing memory to $\mathcal{O}(|V| + |E|)$ .
Adjacency Matrix: Highly efficient for dense graphs ( $∣ E ∣ \approx ∣$ ), providing edge-existence lookups at the cost of space.

5. Paths, Cycles, and Geodesics

To analyze the traversal of networks, we define several types of vertex-edge sequences:

Walk (Path): An alternating sequence of vertices and edges starting at $v_0$ and ending at $v_k$ : $W = v_0, e_1, v_1, e_2, v_2, \dots, e_k, v_k$ The of a walk is the number of edges it contains ().

Geodesics and Distance Metrics

A geodesic is a path of minimum length between two vertices $u$ and $v$ . The distance $d(u, v)$ is the length of this geodesic. The distance metric on an undirected graph satisfies the properties of a metric space:

Reflexivity: $d(u, u) = 0$ .
Symmetry: $d(u, v) = d(v, u)$ .
Triangle Inequality: For any vertices $u, v, w$ :

6. Trees and Their Structural Properties

A tree is an undirected simple graph that is connected and contains no cycles. A forest is a disjoint union of trees.

text

       Rooted Tree                       Binary Tree
          (Root)                            (Root)
            O                                 O
          / | \                              / \
         O  O  O                            O   O
        / \    |                               / \
       O   O   O                              O   O

Rooted Trees and Hierarchy

A rooted tree designates one vertex as the root, with all edges directed away from it. This establishes a family hierarchy:

Parent: The unique vertex immediately preceding a node on the path from the root.
Child: A vertex immediately following a parent node.
Siblings: Vertices that share the same parent.
Ancestors: All vertices on the unique path from the root to the node.
Descendants: All vertices that have the node as an ancestor.
Leaf (Terminal Node): A vertex with no children.
Internal Vertex (Branch Node): A vertex with at least one child.
Level: The length of the path from the root to the node.

Branching Classifications

Ordered Rooted Tree: A rooted tree where the children of each internal node are ordered from left to right.
$m$ -ary Tree: A rooted tree where every internal node has at most $m$ children.
Full $m$ -ary Tree: A tree where every internal node has exactly $m$ children.
Binary Tree: A 2-ary tree where each node has at most a left child and a right child.

Fundamental Tree Theorems

Theorem 1: An undirected graph is a tree if and only if there exists a unique simple path between any two of its vertices.
Theorem 2: A tree with $n$ vertices contains exactly $n - 1$ edges.

Tree Traversals

For ordered rooted trees, we traverse nodes recursively:

Preorder (Root, Left, Right): Visit root, traverse subtrees left-to-right.
Inorder (Left, Root, Right): Traverse left subtree, visit root, traverse remaining subtrees.
Postorder (Left, Right, Root): Traverse subtrees left-to-right, visit root.

7. Special Simple Graphs and Characterization Theorems

Complete Graphs

A complete graph $K_n$ is a simple undirected graph with $n$ vertices where there is an edge between every pair of distinct vertices. The number of edges in $K_n$ is: $E(K_n) = \frac{n(n - 1)}{2}$

Eulerian Paths and Circuits

An Euler path (or Euler circuit) is a trail that traverses every edge in a graph exactly once.

Theorem (Euler Circuit): A connected multigraph has an Euler circuit if and only if every vertex has an even degree.
Theorem (Euler Path): A connected multigraph has an Euler path (but not an Euler circuit) if and only if it has exactly two vertices of odd degree. The path must start at one of the odd-degree vertices and terminate at the other.

This theorem resolved the famous Königsberg Bridges problem, proving that the physical bridge layout could not be traversed without repeating an edge.

Hamiltonian Paths and Circuits

A Hamilton path (or Hamilton circuit) is a simple path that visits every vertex in the graph exactly once. Unlike Eulerian graphs, determining whether a graph is Hamiltonian is NP-complete. However, several sufficient conditions exist:

Dirac's Theorem: If $G$ is a simple graph with $n \ge 3$ vertices, and every vertex $v \in V$ satisfies: $\text{deg}(v) \ge \frac{n}{2}$ then contains a Hamilton circuit.

A classic application of Hamiltonian circuits is the construction of Gray codes, where successive binary code words differ by exactly one bit, corresponding to a Hamiltonian circuit on an $n$ -dimensional hypercube graph $Q_n$ .

8. Planar Graphs, Euler's Formula, and Kuratowski's Theorem

A graph is planar if it can be drawn in a plane such that no edges intersect except at their common endpoints. This drawing is a planar representation of the graph.

text

       Planar Representation             Non-Planar Graph
            of K_4                            (K_5)
 
              A                                 A
             /|\                               /|\ \
            / | \                             / | \ \
           /  |  \                           /  |  \ \
          B---|---C                         B---|---C \
           \  |  /                           \  |  /  /
            \ | /                             \ | /  /
             \|/                               \|/  /
              D                                 D--/

Euler's Formula

When a connected planar graph is drawn, it divides the plane into regions (faces), including one unbounded outer region.

$\text{Euler's Formula: } r = e - v + 2$

where:

$r$ is the number of regions.
$e$ is the number of edges.
$v$ is the number of vertices.

Corollaries and Bounds

These corollaries help prove whether a graph is nonplanar:

Corollary 1: For any connected planar simple graph with $v \ge 3$ vertices: $e \le 3v - 6$
Corollary 2: If a connected planar simple graph has no cycles of length 3 (e.g., a bipartite graph) and $v \ge 3$ : $e \le 2v - 4$

Elementary Subdivision: Introducing a new vertex of degree 2 into an existing edge, effectively splitting the edge into two.
Homeomorphism: Two graphs are homeomorphic if both can be obtained from the same graph by a sequence of elementary subdivisions.

text

        Original Edge                After Elementary Subdivision
         u -------- v                 u ---- w ---- v

Kuratowski's Theorem: A graph is planar if and only if it does not contain a subgraph that is homeomorphic to $K_5$ or $K_{3,3}$ .

9. Applications of Graph Theory

Graph-theoretic models are used to solve complex engineering and computing challenges:

Job Assignment and Matchings: Representing employees and available roles as a bipartite graph. Finding optimal job assignments corresponds to finding a maximum matching in the graph.
Local Area Network (LAN) Topologies: Modeling computer networks using physical structures like Star (tree-like), Ring (Hamiltonian cycle), or Hybrid designs to optimize communication and fault tolerance.
Parallel Computation Routing: In parallel processing architectures, processors are modeled as vertices and their high-speed communication channels as edges. Designs like linear arrays, mesh networks, or hypercubes are used to balance communication latency with physical wiring limits.
Chemical Structure Analysis: Modeling molecules as graphs where vertices represent atoms and edges represent chemical bonds. Isomorphic graph detection helps identify equivalent chemical compounds (isomers).

Summary

Graph Fundamentals: Graphs are composed of vertices and edges. They can be directed or undirected, simple, weighted, or multigraphs.
Connectivity: Reachability and node bases identify structural dependencies. Cut vertices and bridges represent single points of failure.
Matrix Representations: Adjacency and incidence matrices map graph topologies to algebra. The matrix powers $A^k$ count the number of paths of length $k$ .
Trees: Trees are connected acyclic graphs with $n-1$ edges. They are structured using parent-child hierarchies and traversed via preorder, inorder, and postorder algorithms.
Classical Traversals: Euler circuits require all vertices to have an even degree. Hamilton circuits visit every vertex exactly once, governed by Dirac's and Ore's degree-based conditions.
Planarity: Planar graphs must satisfy Euler's formula ( $r = e -$ ). Under Kuratowski's Theorem, planarity is lost if a graph contains a subgraph homeomorphic to or .

Assessed progress

Special Graphs, Planarity, and Theorems

Key Concepts

Graph Isomorphism and Invariants

Strong and Weak Connectivity

Matrix Representations and Path Counts

Eulerian and Hamiltonian Systems

Planarity and Kuratowski's Theorem

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures