Unit 5: Graph Theory with Applications

Table of Contents

5.1 Basic Concepts of Graph Theory

A graph G = (V, E) is a set of vertices V and a set of edges E.

5.2 Isomorphism and Homomorphism

  • Isomorphism: Two graphs G1 and G2 are isomorphic if there is a bijective (one-to-one and onto) function f: V(G1) \to V(G2) that preserves adjacency. That is, (u, v) is an edge in G1 if and only if (f(u), f(v)) is an edge in G2.
    To prove non-isomorphism: Find a property they don't share (e.g., number of vertices, number of edges, degree sequence, number of cycles of a certain length).
  • Homomorphism: A map f: V(G1) \to V(G2) is a homomorphism if (u, v) ∈ E(G1) implies (f(u), f(v)) ∈ E(G2). It's a structure-preserving map that is not necessarily bijective.

5.3 Subgraphs, Union, Multigraphs, Weighted Graphs

  • Subgraph: A graph H is a subgraph of G if V(H) ⊂eq V(G) and E(H) ⊂eq E(G).
  • Union of graphs: G1 ∪ G2 = (V1 ∪ V2, E1 ∪ E2).
  • Multigraph: A graph that allows multiple edges (parallel edges) between the same pair of vertices.
  • Weighted Graph: A graph where a number (weight or cost) is assigned to each edge.

5.4 Planar Graphs

A planar graph is a graph that can be drawn on a plane in such a way that no two edges cross each other.

Euler's Formula: For any connected planar graph, v - e + f = 2, where v is the number of vertices, e is the number of edges, and f is the number of faces (regions, including the outer region).

5.5 Walks, Paths, and Circuits

  • Walk: A sequence of alternating vertices and edges, e.g., v0, e1, v1, e2, v2, ..., vk. Edges and vertices can be repeated.
  • Path: A walk in which all vertices are distinct (and thus all edges are also distinct).
  • Circuit (or Cycle): A closed walk (starts and ends at the same vertex) in which all vertices are distinct, except for the start/end vertex. A cycle must have length 3 or more.

5.6 Components, Connectedness, Cut-sets, Cut-vertices

  • Connectedness: A graph is connected if there is a path between every pair of distinct vertices.
  • Components: The connected subgraphs of a disconnected graph are its components.
  • Cut-vertex (Articulation Point): A vertex whose removal increases the number of connected components.
  • Cut-set (or Bridge): An edge whose removal increases the number of connected components. A cut-set can be a set of edges.

5.7 Eulerian and Hamiltonian Graphs

Eulerian Graph

  • An Eulerian circuit is a circuit that traverses every edge exactly once.
  • An Eulerian path is a path that traverses every edge exactly once.
  • Theorem: A connected graph has an Eulerian circuit if and only if every vertex has an even degree. It has an Eulerian path if and only if it has exactly two vertices of odd degree (the path must start at one and end at the other).

Hamiltonian Graph

  • A Hamiltonian cycle is a cycle that visits every vertex exactly once.
  • A Hamiltonian path is a path that visits every vertex exactly once.
  • Note: Unlike Euler circuits, there is no simple, necessary, and sufficient condition to determine if a graph has a Hamiltonian cycle. This is a much harder problem (NP-complete).
Common Mistake: Confusing Euler and Hamilton.
  • Euler: All Edges. Check Even degrees. (Easy)
  • Hamilton: All Vertices (H is 'near' V in alphabet... sort of). No simple check. (Hard)

5.8 Complete, Regular, and Bipartite Graphs

  • Complete Graph (Kn): A simple graph with n vertices where every vertex is connected to every other vertex. It has n(n-1)/2 edges.
  • Regular Graph: A graph where every vertex has the same degree. A graph is k-regular if d(v) = k for all v ∈ V.
  • Bipartite Graph: A graph whose vertex set V can be partitioned into two disjoint sets, V1 and V2, such that every edge connects a vertex in V1 to one in V2. (No edges *within* V1 or V2).
    • Theorem: A graph is bipartite if and only if it contains no odd-length cycles.
    • Complete Bipartite Graph (Km,n): A bipartite graph with |V1|=m and |V2|=n, containing all m × n possible edges between V1 and V2.