6.1 Fundamentals of Graph Theory

Graph theory is the backbone of many complex systems we encounter daily. From social networks to transportation routes, graphs help us model and analyze connections between entities. Understanding fundamental concepts like vertices, edges, and graph types is crucial for tackling more advanced topics in algebraic graph theory.

This section covers essential graph theory concepts, including graph types, connectivity, and traversal algorithms. These foundational ideas provide the groundwork for exploring algebraic properties of graphs, such as spectral graph theory and graph isomorphisms, which we'll dive into later in the chapter.

Basic Graph Theory Concepts

Graph Fundamentals

• A graph is a mathematical structure consisting of a set of vertices (also called nodes) and a set of edges connecting pairs of vertices
• Vertices represent objects or entities, while edges represent relationships or connections between the vertices
• Graphs can be represented using various data structures, such as adjacency matrices or adjacency lists
• The order of a graph is the number of vertices, and the size of a graph is the number of edges

Vertex Degrees

• The degree of a vertex is the number of edges incident to it
  • In an undirected graph, the degree is simply the number of edges connected to the vertex
  • In a directed graph, the in-degree is the number of incoming edges, and the out-degree is the number of outgoing edges
• The handshaking lemma states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges
• In a regular graph, all vertices have the same degree (cubic graph, where each vertex has degree 3)

Graph Types

Simple and Multigraphs

• Simple graphs have no self-loops (edges connecting a vertex to itself) and no multiple edges between the same pair of vertices
• Multigraphs allow multiple edges between the same pair of vertices but do not allow self-loops
  • Example: a transportation network where multiple roads or flights connect two cities
• Pseudographs are a generalization of multigraphs that allow both multiple edges and self-loops

Directed and Weighted Graphs

• Directed graphs (digraphs) consist of a set of vertices and a set of directed edges, where each edge has a specific direction from one vertex to another
  • Example: a social network where edges represent "following" relationships
• Weighted graphs assign a numerical value (weight) to each edge, representing the cost, distance, or some other attribute associated with the connection
  • Example: a road network where weights represent the distance or travel time between cities

Special Graph Types

• Complete graphs have an edge between every pair of vertices, denoted as $K_n$ for a graph with $n$ vertices
• Empty graphs have no edges at all, consisting only of isolated vertices
• Bipartite graphs have their vertex set divided into two disjoint subsets, with edges only connecting vertices from different subsets
  • Example: a graph representing students and courses, where edges connect students to the courses they are enrolled in
• Trees are connected graphs with no cycles, often used in hierarchical structures (binary trees, decision trees)

Graph Connectivity

Paths and Cycles

• A path is a sequence of vertices connected by edges, where no vertex is repeated
  • The length of a path is the number of edges in the sequence
  • A simple path is a path with no repeated vertices
• A cycle is a path that starts and ends at the same vertex, with no other repeated vertices
  • A simple cycle is a cycle with no repeated vertices (except for the start/end vertex)
• Eulerian paths and cycles:
  • An Eulerian path is a path that uses every edge of the graph exactly once
  • An Eulerian cycle is a cycle that uses every edge of the graph exactly once
  • A graph has an Eulerian cycle if and only if it is connected and every vertex has an even degree

Connected Components

• A graph is connected if there exists a path between every pair of vertices
  • Otherwise, it is disconnected and consists of multiple connected components
• A connected component is a maximal connected subgraph, meaning it is not a proper subgraph of any other connected subgraph
• The number of connected components in a graph can be determined using graph traversal algorithms (DFS or BFS)

Distance and Diameter

• The distance between two vertices is the length of the shortest path between them
  • If there is no path between the vertices, the distance is considered infinite
• The eccentricity of a vertex is the maximum distance from that vertex to any other vertex in the graph
• The diameter of a graph is the maximum distance between any pair of vertices in the graph
  • Equivalently, it is the maximum eccentricity among all vertices
• The radius of a graph is the minimum eccentricity among all vertices

Cut Vertices and Bridges

• A cut vertex (or articulation point) is a vertex whose removal increases the number of connected components in the graph
  • Cut vertices can be identified using DFS and keeping track of discovery and low times
• A bridge (or cut edge) is an edge whose removal increases the number of connected components in the graph
  • Bridges can be identified using DFS and keeping track of discovery times and parent vertices
• The connectivity of a graph is the minimum number of vertices that need to be removed to disconnect the graph
  • A graph is $k$-connected if it remains connected after removing any $k-1$ vertices

Graph Traversal Algorithms

Depth-First Search (DFS)

• Depth-first search (DFS) explores as far as possible along each branch before backtracking
• DFS uses a stack (often implemented recursively) to keep track of the vertices to visit next
• The time complexity of DFS is $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges
• Applications of DFS:
  • Detecting cycles in a graph
  • Finding connected components
  • Topological sorting of a directed acyclic graph (DAG)
  • Solving maze or puzzle problems

Breadth-First Search (BFS)

• Breadth-first search (BFS) explores all the neighboring vertices at the current depth before moving on to the vertices at the next depth level
• BFS uses a queue to keep track of the vertices to visit next
• The time complexity of BFS is $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges
• Applications of BFS:
  • Finding the shortest path between two vertices in an unweighted graph
  • Determining the connected components of a graph
  • Solving problems related to the shortest distance or levels (e.g., social network analysis)

Advanced Traversal Techniques

• Topological sorting: ordering the vertices of a directed acyclic graph (DAG) such that for every directed edge $(u, v)$, vertex $u$ comes before vertex $v$ in the ordering
  • Can be achieved using a modified DFS algorithm
• Strongly connected components (SCCs): maximal subgraphs of a directed graph where there is a path from each vertex to every other vertex in the subgraph
  • Tarjan's algorithm and Kosaraju's algorithm are used to find SCCs
• Bipartite graph checking: determining if a graph can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set
  • Can be done using a modified BFS or DFS algorithm, assigning colors to vertices