Unit 4: Graphs Theory I

MTH401 — Discrete Mathematics 8 min read

I. Foundations of Graph Theory

Graph theory studies structures consisting of objects and the pairwise relationships between them. Its foundations are commonly traced to Leonhard Euler’s solution of the Königsberg bridge problem (1736), in which land regions were represented by vertices and bridges by edges.

Basic model: A graph is an ordered pair (G=(V,E)), where (V) is a nonempty set of vertices and (E) is a set of edges joining vertices.
Order and size: The order of (G) is (|V|), while its size is (|E|).
Undirected convention: An edge joining (u) and (v) is an unordered pair ({u,v}), usually written (uv).
Directed convention: A directed edge is an ordered pair ((u,v)), directed from (u) to (v).
Simple-graph assumption: Unless stated otherwise, graphs are often assumed to have no loops and no parallel edges.
Finite-graph assumption: Most elementary results concern graphs with finite vertex and edge sets.
Central questions: Graph theory examines adjacency, degree, structural equivalence, paths, connectivity, and optimization over networks.

II. Graph Terminologies — Fundamental Vocabulary

A. Graph terminologies

Graph terminology identifies the elements of a graph and the relationships among them.

Vertex and edge: A vertex represents an object, while an edge represents a relationship. For
[
G=({a,b,c},{{a,b},{b,c}}),
]
the vertices are (a,b,c), and the edges are (ab) and (bc).
Adjacent vertices: Vertices (u) and (v) are adjacent if (uv\in E); (u) and (v) are then called neighbors.
Incident edge: Edge (uv) is incident with both (u) and (v).
Degree: The degree (\deg(v)) is the number of edges incident with (v). A loop, when permitted, contributes (2) to the degree.
Isolated and pendant vertices:
- An isolated vertex has degree (0).
- A pendant or leaf vertex has degree (1).
Handshaking lemma: In every finite undirected graph,
TEXT
```
  Σ deg(v) = 2|E|
  v∈V
```
Consequently, the number of odd-degree vertices is even.
Directed degree: In a digraph, (\deg^-(v)) is the indegree and (\deg^+(v)) is the outdegree.
TEXT
```
  Σ deg⁻(v) = Σ deg⁺(v) = |E|
```
Loop and parallel edges: A loop joins a vertex to itself; parallel edges have the same endpoints. A multigraph may contain parallel edges.
Subgraph: (H=(V_H,E_H)) is a subgraph of (G) when (V_H\subseteq V) and (E_H\subseteq E).
Complement: For a simple graph (G), its complement (\overline G) has the same vertices, with (uv\in E(\overline G)) exactly when (uv\notin E(G)) and (u\ne v).

III. Special Graph Families — Standard Structural Forms

A. Special types of graphs: complete, cycle, regular, wheel, cube, bipartite and complete bipartite

Special graph families are defined by recurring patterns of adjacency and degree.

Complete graph: (K_n) is a simple graph in which every pair of distinct vertices is adjacent.
TEXT
```
  |E(Kₙ)| = n(n − 1)/2,      deg(v) = n − 1
```
For example, (K_4) has (4) vertices and (6) edges.
Cycle graph: (C_n), for (n\ge 3), consists of one closed cycle through all (n) vertices.
TEXT
```
  |E(Cₙ)| = n,      deg(v) = 2
```
Regular graph: A graph is (r)-regular if every vertex has degree (r). By the handshaking lemma,
TEXT
```
  nr = 2|E|
```
where (n=|V|); therefore (nr) must be even.
Wheel graph: A wheel (Wn) is formed by adding a central hub adjacent to every vertex of a cycle (C{n-1}), under the convention that (W_n) has (n) vertices.
TEXT
```
  |E(Wₙ)| = 2(n − 1)
```
The hub has degree (n-1), and each rim vertex has degree (3).
Cube graph: The (n)-cube (Q_n) has all binary strings of length (n) as vertices; two strings are adjacent when they differ in exactly one position.
TEXT
```
  |V(Qₙ)| = 2ⁿ,      |E(Qₙ)| = n2ⁿ⁻¹
```
Thus (Q_3) has (8) vertices, (12) edges, and degree (3) at every vertex.
Bipartite graph: A graph is bipartite if (V) can be divided into disjoint sets (X) and (Y) such that every edge has one endpoint in each set. A graph is bipartite exactly when it contains no odd cycle.
Complete bipartite graph: (K_{m,n}) has partite sets of sizes (m) and (n), with every vertex in one set adjacent to every vertex in the other.
TEXT
```
  |V| = m+n,      |E| = mn
```
Vertices in the first set have degree (n), while those in the second have degree (m).

IV. Graph Representation — Storing Structural Information

A. Representing graphs

A graph can be represented visually or through data structures chosen according to the required operations.

Graph drawing: Vertices are drawn as points and edges as lines or arrows. Position and edge crossings normally have no mathematical significance.
Edge list: Store every edge as a pair such as ((u,v)). It requires (O(|E|)) space and is convenient for processing all edges.
Adjacency list: Store, for each vertex (u), a list of its neighbors. It uses (O(|V|+|E|)) space for an undirected simple graph.
Directed adjacency list: The list for (u) normally contains vertices (v) for which ((u,v)\in E); these are the out-neighbors of (u).
Choice of representation: Adjacency lists suit sparse graphs, while matrices provide constant-time adjacency checks and suit dense graphs.

V. Matrix Representations — Algebraic Descriptions

A. Adjacency and incidence matrix

Adjacency and incidence matrices encode graph relationships in tabular form.

Adjacency matrix
- Definition: For vertices (v_1,\ldots,vn), the adjacency matrix (A=[a{ij}]) is defined by
  TEXT
```
     aᵢⱼ = 1 if vᵢ is adjacent to vⱼ,
            0 otherwise.
```
- Properties: For a simple undirected graph, (A) is symmetric and its main diagonal contains zeros.
- Degrees: The sum of row (i) equals (\deg(v_i)). In a digraph, row sums give outdegrees and column sums give indegrees.
- Walk counting: The entry ((A^k)_{ij}) counts walks of length (k) from (v_i) to (v_j).
Incidence matrix
- Definition: For vertices (v_1,\ldots,v_n) and edges (e_1,\ldots,em), (B=[b{ij}]) has
  TEXT
```
     bᵢⱼ = 1 if vertex vᵢ is incident with edge eⱼ,
            0 otherwise.
```
- Undirected structure: Each column of a loopless undirected graph contains exactly two (1)s.
- Directed convention: A signed incidence matrix commonly uses (-1) at an edge’s tail, (+1) at its head, and (0) elsewhere.

VI. Graph Isomorphism — Structural Equivalence

A. Graph isomorphism

Two graphs are isomorphic when they have the same adjacency structure despite different vertex names or drawings.

Formal definition: Graphs (G=(V_G,E_G)) and (H=(V_H,E_H)) are isomorphic if a bijection (f:V_G\to V_H) satisfies
TEXT
```
  uv ∈ E_G ⇔ f(u)f(v) ∈ E_H.
```
Preserved invariants: Isomorphic graphs have equal numbers of vertices and edges, identical degree multisets, equal numbers of components, and equal cycle structures.
Necessary versus sufficient: Matching invariants are necessary but may not prove isomorphism; an explicit adjacency-preserving bijection is sufficient.
Matrix criterion: If (A_G) and (A_H) are adjacency matrices, the graphs are isomorphic exactly when some permutation matrix (P) satisfies
TEXT
```
  A_H = PᵀA_GP.
```
Disproof method: A difference in any invariant, such as one graph containing a triangle while the other does not, proves non-isomorphism.

VII. Paths and Connectivity — Reachability in Networks

A. Path and connectivity for undirected graphs and digraphs

Paths describe movement through a graph, while connectivity determines whether vertices can reach one another.

Undirected graphs
- Walk, trail, and path: A walk may repeat vertices and edges; a trail repeats no edge; a path repeats no vertex.
- Length: The length is the number of edges traversed. A path (v_0,v_1,\ldots,v_k) has length (k).
- Connected graph: An undirected graph is connected if a path exists between every pair of vertices.
- Components: A connected component is a maximal connected subgraph.
- Cut structures: Removing a cut vertex or bridge increases the number of connected components.
Digraphs
- Directed path: Every edge must follow its orientation, so ((v_{i-1},v_i)\in E) at each step.
- Strong connectivity: A digraph is strongly connected if directed paths exist from (u) to (v) and from (v) to (u) for every pair (u,v).
- Weak connectivity: A digraph is weakly connected if replacing directed edges by undirected edges produces a connected graph.
- Reachability: Vertex (v) is reachable from (u) when a directed path from (u) to (v) exists; reachability need not be symmetric.

VIII. Dijkstra’s Algorithm — Single-Source Shortest Paths

A. Dijkstra's algorithm for shortest path problem

Dijkstra’s algorithm finds shortest paths from one source to all vertices in a weighted graph whose edge weights are nonnegative.

Distance estimate: Maintain (d[v]), the best known distance from source (s) to vertex (v), and (\operatorname{pred}[v]), its predecessor.

Initialization:

TEXT

  d[s] = 0
  d[v] = ∞ for every v ≠ s
  pred[v] = undefined

Greedy selection: Repeatedly choose the unsettled vertex (u) with minimum (d[u]). With nonnegative weights, this distance is then final.

Relaxation: For every outgoing edge ((u,v)) of weight (w(u,v)), test