Unit 4: Graph Theory-I

Graph theory studies pairwise relations between objects using vertices (points) and edges (links). A graph abstracts away everything except what is connected to what, making it the natural model for networks, circuits, maps, and dependencies. Formally a graph is an ordered pair G = (V, E) where V is a finite nonempty set of vertices and E is a set of edges, each associating two vertices.

• Vertex (node): a fundamental element of V; e.g. V = {a, b, c}.
• Edge (arc): a connection {u, v} joining two vertices; the vertices are its endpoints.
• Adjacent vertices: two vertices joined by an edge; u and v are adjacent if {u, v} ∈ E.
• Incident: an edge e = {u, v} is incident on u and on v.
• Loop: an edge whose two endpoints coincide, {v, v}.
• Parallel (multiple) edges: two or more edges sharing the same pair of endpoints.
• Order and size: order = |V| (number of vertices); size = |E| (number of edges).
• Directed vs undirected: in a digraph edges are ordered pairs (u, v); unless stated otherwise, graphs here are undirected.

II. Graphs and Multigraphs

Types of graph differ by whether loops and parallel edges are permitted.

A. Graphs

A simple graph has no loops and no parallel edges — every edge is a distinct unordered pair of distinct vertices.

• Simple graph: E ⊆ { {u, v} : u, v ∈ V, u ≠ v }. Between any two vertices there is at most one edge.
• Maximum size: a simple graph on n vertices has at most C(n, 2) = n(n−1)/2 edges.
• Complete graph Kₙ: every pair of vertices adjacent; size = n(n−1)/2. K₄ has 6 edges.
• Regular graph: every vertex has the same degree; a k-regular graph has all degrees = k.
• Bipartite graph: V splits into V₁, V₂ with every edge running between the parts, none within; Kₘ,ₙ is the complete bipartite graph.
• Null / empty graph Nₙ: n vertices, no edges.

B. Multigraphs

A multigraph relaxes the simple-graph rules to allow repeated or self-connections, so E becomes a multiset.

• Parallel edges allowed: two vertices may be joined by several edges — models roads with multiple lanes or repeated relations.
• Pseudograph: a multigraph that also permits loops.
• Edge multiplicity: the number of parallel edges between a pair; multiplicity > 1 distinguishes a multigraph from a simple graph.
• Contrast:
  1. Simple graph: loops forbidden, multiplicity ≤ 1.
  2. Multigraph / pseudograph: multiplicity ≥ 1, loops allowed in the pseudograph case.

III. Degrees and the Handshaking Theorem

Degree counts local connectivity and links directly to edge count.

A. Degree of a vertex

The degree deg(v) is the number of edge-ends meeting at v.

• Definition: number of edges incident on v, with a loop counted twice.
• Isolated vertex: deg(v) = 0; pendant (leaf) vertex: deg(v) = 1.
• Minimum and maximum degree: written δ(G) and Δ(G).
• Directed graphs: split into in-degree deg⁻(v) (edges entering) and out-degree deg⁺(v) (edges leaving); deg(v) = deg⁻(v) + deg⁺(v).
• Degree sequence: the list of all vertex degrees, usually written in non-increasing order, e.g. (3, 3, 2, 2, 2).

B. Handshaking Theorem

The sum of all degrees equals twice the number of edges, because each edge contributes to exactly two degree counts.

Σ deg(v) = 2|E|      (sum taken over all v ∈ V)

• Symbol meaning: Σ deg(v) totals every vertex degree; |E| is the number of edges.
• Why "2": each edge has two ends, adding 1 to the degree at each endpoint (a loop adds 2 at one vertex).
• Corollary — even count of odd-degree vertices: the number of vertices with odd degree is always even, since the odd contributions must pair up to give an even total.
• Worked example: a graph with degree sequence (3, 3, 2, 2, 2) has Σ deg = 12, so |E| = 12 / 2 = 6 edges; the two odd-degree vertices form an even count, as required.

IV. Subgraphs and Structural Equivalence

Graphs are compared by extracting parts and by matching whole structures.

A. Sub graphs

A subgraph H = (V', E') of G = (V, E) satisfies V' ⊆ V and E' ⊆ E, with every edge of H having both endpoints in V'.

• Spanning subgraph: V' = V (all vertices kept, some edges possibly dropped).
• Induced subgraph G[V']: take a vertex subset V' and all edges of G whose endpoints both lie in V'.
• Vertex/edge deletion: G − v removes v and all edges on it; G − e removes just edge e.
• Clique: a subset of mutually adjacent vertices — an induced complete subgraph.

B. Homeomorphic and isomorphic graphs

Two notions of "the same shape": one is exact relabelling, the other is equivalence up to subdivided edges.

• Isomorphism: a bijection f : V(G) → V(H) preserving adjacency, i.e. {u, v} ∈ E(G) ⇔ {f(u), f(v)} ∈ E(H).
  • Invariants that must match: order, size, degree sequence, number of components, cycle lengths — mismatch in any proves non-isomorphism.
  • Equal invariants do not guarantee isomorphism; the explicit bijection must still be exhibited.
• Edge subdivision: replacing an edge {u, v} by a new vertex w and two edges {u, w}, {w, v} — a degree-2 vertex inserted on the edge.
• Homeomorphism: graphs G and H are homeomorphic if both can be obtained from a common graph by a sequence of edge subdivisions; they share the same underlying topological structure.
  1. Isomorphic: identical structure, degrees preserved exactly.
  2. Homeomorphic: identical after smoothing out degree-2 vertices — every triangle is homeomorphic to every larger cycle.

V. Paths, Connectivity and Components

These describe reachability — how vertices link through sequences of edges.

A. Paths

A path is a walk that traverses distinct vertices, tracing a route through the graph.

• Walk: an alternating vertex–edge sequence v₀ e₁ v₁ … eₖ vₖ; length = number of edges k.
• Trail: a walk with no repeated edge; path: a walk with no repeated vertex.
• Cycle (circuit): a closed path with v₀ = vₖ and length ≥ 1 (or ≥ 3 in a simple graph).
• Reachability: v is reachable from u if some path joins them.

B. Connectivity

A graph is connected when there is a path between every pair of vertices.

• Connected graph: for all u, v ∈ V, a u–v path exists; otherwise disconnected.
• Vertex connectivity κ(G): the minimum number of vertices whose removal disconnects G (or reduces it to one vertex).
• Edge connectivity λ(G): the minimum number of edges whose removal disconnects G.
• Whitney's inequality: κ(G) ≤ λ(G) ≤ δ(G) — connectivity is bounded by the least degree.

C. Connected components

A connected component is a maximal connected subgraph — a piece that cannot be enlarged while staying connected.

• Partition: components partition V; every vertex lies in exactly one component.
• Connected ⇔ one component: G is connected precisely when its component count is 1.
• Example: a graph with vertices {a,b,c,d,e} and edges {a,b}, {b,c}, {d,e} has two components — {a,b,c} and {d,e}.

VI. Distance, Diameter and Critical Elements

Metric and vulnerability measures on a connected graph.

A. Distance and diameter

Distance measures the shortest hop-count between vertices; diameter is the largest such distance.

• Distance d(u, v): the length of the shortest u–v path; d(u, v) = ∞ if none exists.
• Metric properties: d(u,u)=0; d(u,v)=d(v,u); triangle inequality d(u,w) ≤ d(u,v)+d(v,w).
• Eccentricity e(v): the greatest distance from v to any other vertex, e(v)=max_{u} d(v,u).
• Diameter: diam(G) = max_{v} e(v) — the largest eccentricity; radius = min_{v} e(v).
• Example: in path graph P₄ (a–b–c–d), d(a,d)=3, so diam(P₄)=3.

B. Cut points and bridges

A cut point is a critical vertex and a bridge a critical edge whose removal breaks connectivity.

• Cut point (cut vertex / articulation point): a vertex v such that G − v has more components than G.
• Bridge (cut edge): an edge e such that G − e has more components than G.
• Bridge test: an edge is a bridge iff it lies on no cycle — a cycle always provides an alternate route.
  1. Cut point: local single point of failure at a vertex; removing it isolates a set of vertices.
  2. Bridge: single point of failure along an edge; the only link between two parts of the graph.
• Example: in the graph a–b–c with edges {a,b}, {b,c}, vertex b is a cut point and both edges are bridges, since removing either separates the endpoints.