🧮Combinatorics Unit 11 – Paths, Cycles, and Connectivity in Graphs

Key Concepts and Definitions

• Graphs consist of a set of vertices (nodes) and a set of edges connecting pairs of vertices
• Paths are sequences of vertices connected by edges with no repeated vertices
• Cycles are paths that start and end at the same vertex
• Connected graphs have a path between every pair of vertices
• Components are maximal connected subgraphs
  • Maximal means adding any other vertex would make the subgraph disconnected
• Bridges (cut-edges) are edges whose removal increases the number of components in a graph
  • Removing a bridge disconnects the graph
• Articulation points (cut-vertices) are vertices whose removal increases the number of components
  • Removing an articulation point disconnects the graph

Graph Basics and Terminology

• Graphs are denoted as $G = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges
• Edges can be undirected (unordered pairs of vertices) or directed (ordered pairs)
• The degree of a vertex is the number of edges incident to it
  • In directed graphs, vertices have in-degrees (incoming edges) and out-degrees (outgoing edges)
• Adjacent vertices are directly connected by an edge
• Incident edges share a common vertex
• Subgraphs are formed by selecting a subset of vertices and edges from the original graph
• Induced subgraphs include all edges between the selected vertices in the original graph

Types of Paths and Cycles

• Simple paths have no repeated vertices or edges
• Elementary paths may have repeated vertices but no repeated edges
• Hamiltonian paths visit every vertex in the graph exactly once
  • Hamiltonian cycles are Hamiltonian paths that start and end at the same vertex
• Eulerian paths traverse every edge in the graph exactly once
  • Eulerian cycles are Eulerian paths that start and end at the same vertex
• Shortest paths minimize the total weight or distance between two vertices
• Longest paths maximize the total weight or distance between two vertices

Connectivity in Graphs

• Connectivity measures how well-connected a graph is
• Vertex connectivity ($\kappa(G)$) is the minimum number of vertices whose removal disconnects the graph
  • A graph is $k$-vertex-connected if $\kappa(G) \geq k$
• Edge connectivity ($\lambda(G)$) is the minimum number of edges whose removal disconnects the graph
  • A graph is $k$-edge-connected if $\lambda(G) \geq k$
• Whitney's Theorem states that for any graph $G$, $\kappa(G) \leq \lambda(G) \leq \delta(G)$, where $\delta(G)$ is the minimum degree of $G$
• Menger's Theorem relates connectivity to the number of disjoint paths between vertices
  • There are at least $k$ vertex-disjoint paths between any two non-adjacent vertices if and only if the graph is $k$-vertex-connected

Algorithms for Finding Paths and Cycles

• Depth-First Search (DFS) explores a graph by going as deep as possible before backtracking
  • DFS can be used to find connected components, bridges, and articulation points
• Breadth-First Search (BFS) explores a graph level by level, visiting all neighbors before moving to the next level
  • BFS can be used to find shortest paths in unweighted graphs
• Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights
• Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph
• Fleury's algorithm finds an Eulerian path or cycle in a graph, if one exists
• Hierholzer's algorithm constructs an Eulerian cycle by repeatedly removing cycles until the graph is empty

Applications in Real-world Problems

• Network flow problems involve finding the maximum flow from a source to a sink in a directed graph with edge capacities
  • Applications include transportation networks, communication networks, and supply chain management
• Matching problems aim to find a set of edges with no shared vertices
  • Applications include assigning tasks to workers, pairing students for projects, and finding stable marriages
• Graph coloring assigns colors to vertices such that no adjacent vertices have the same color
  • Applications include scheduling conflicts, map coloring, and frequency assignment in wireless networks
• Traveling Salesman Problem (TSP) seeks to find the shortest tour that visits every vertex exactly once
  • Applications include route planning, circuit board drilling, and DNA sequencing

Common Theorems and Proofs

• Euler's Theorem characterizes the existence of Eulerian paths and cycles
  • A connected graph has an Eulerian cycle if and only if every vertex has even degree
  • A connected graph has an Eulerian path if and only if exactly two vertices have odd degree
• Ore's Theorem provides a sufficient condition for a graph to be Hamiltonian
  • If for every pair of non-adjacent vertices $u$ and $v$, $\deg(u) + \deg(v) \geq n$, then the graph is Hamiltonian
• Dirac's Theorem states that if a graph has $n \geq 3$ vertices and minimum degree $\delta(G) \geq \frac{n}{2}$, then the graph is Hamiltonian
• Kuratowski's Theorem characterizes planar graphs
  • A graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_{3,3}$
• Hall's Marriage Theorem relates the existence of perfect matchings to the size of vertex subsets
  • A bipartite graph with partite sets $X$ and $Y$ has a perfect matching if and only if $|N(S)| \geq |S|$ for every subset $S \subseteq X$, where $N(S)$ is the set of neighbors of $S$ in $Y$

Practice Problems and Examples

• Determine if a given graph is connected, and find its connected components if it is not
• Find all bridges and articulation points in a graph
• Determine if a graph has an Eulerian path or cycle, and find one if it exists
• Find the shortest path between two vertices in a weighted graph using Dijkstra's algorithm
• Determine if a graph is Hamiltonian using Ore's or Dirac's Theorem
• Find a perfect matching in a bipartite graph, or prove that one does not exist using Hall's Theorem
• Prove that a given graph is planar or non-planar using Kuratowski's Theorem
• Solve a network flow problem by finding the maximum flow from a source to a sink