Graph theory - Graph Structures Representation and Core Problems

Representations of Graphs and Fundamental Graph Problems Introduction Before you can solve problems on graphs, you need two things: (1) a way to represent graphs in your computer or on paper, and (2) an understanding of the key problems that arise in graph theory. This guide covers both the practical data structures used to store graphs and the fundamental problems that computer scientists and mathematicians care about. Understanding these foundational concepts will prepare you to solve graph problems efficiently and recognize when a problem is computationally hard. Representing Graphs Why Representations Matter When you draw a graph with vertices and edges on paper, it looks clear and intuitive. But a computer doesn't understand drawings. We need to encode graphs as data structures so algorithms can manipulate them. Different representations have different trade-offs: some are compact, some make certain operations fast, and some are simply easier to work with for specific problems. List Structures The simplest way to store a graph is with an edge list. This structure stores every edge exactly once as a pair of vertices. Example: For a graph with edges connecting (1,2), (2,3), and (1,3), the edge list would contain: Edge 1: vertices 1 and 2 Edge 2: vertices 2 and 3 Edge 3: vertices 1 and 3 Edge lists are space-efficient (using $O(|E|)$ space where $|E|$ is the number of edges) but checking whether a specific edge exists requires scanning through the entire list. More useful for many algorithms is an adjacency list. For each vertex, this structure maintains a list of all vertices adjacent to it (i.e., connected by an edge). Example: For the same graph above, the adjacency list would be: Vertex 1: [2, 3] Vertex 2: [1, 3] Vertex 3: [1, 2] Adjacency lists are excellent for graph traversal algorithms (like depth-first search) because finding all neighbors of a vertex is very fast. They also use $O(|V| + |E|)$ space, which is typically efficient. Matrix Structures When you need faster lookups or want to perform algebraic operations on graphs, matrix representations are ideal. The adjacency matrix $A$ is a square matrix of size $|V| \times |V|$ where: $A{ij} = 1$ if vertices $i$ and $j$ are adjacent (connected by an edge) $A{ij} = 0$ otherwise For an undirected graph, the adjacency matrix is symmetric: $A{ij} = A{ji}$. Example: The adjacency matrix for our graph is: $$A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$$ Checking if two vertices are adjacent is now instant (constant time), but the matrix uses $O(|V|^2)$ space, which can be wasteful for sparse graphs (graphs with few edges). Beyond adjacency matrices, several other important matrix representations exist: The degree matrix $D$ is a diagonal matrix where $D{ii}$ equals the degree of vertex $i$ (the number of edges connected to it). This is useful in combination with the adjacency matrix. The Laplacian matrix is defined as $L = D - A$. This matrix has special properties: the sum of each row is zero, and its eigenvalues encode information about graph structure. The Laplacian appears in many graph algorithms, particularly those related to spectral methods and community detection. The distance matrix stores the length of the shortest path between every pair of vertices. The entry at position $(i,j)$ is the shortest path distance from vertex $i$ to vertex $j$. This is useful when you care about how "far apart" vertices are. The incidence matrix records which vertices are incident to (connected to) each edge. It's a $|V| \times |E|$ matrix where the $(i,j)$ entry is 1 if vertex $i$ is an endpoint of edge $j$, and 0 otherwise. Planarity and Crossing Number A fundamental question in graph theory is: can this graph be drawn on a plane without any edges crossing? The crossing number of a graph is the minimum number of edge crossings that must occur in any drawing of the graph. A planar graph is simply a graph whose crossing number is zero—it can be drawn on a plane with no edges crossing. Planarity matters because: Planar graphs model real-world problems like circuit design (where you can't have wires crossing) and map coloring Planar graphs have special structural properties that non-planar graphs lack Testing whether a graph is planar is computationally efficient (can be done in linear time) Two graphs play a special role in characterizing planarity: $K5$: the complete graph on 5 vertices (every vertex connected to every other) $K{3,3}$: the complete bipartite graph with 3 vertices in each part (a bipartite graph where every vertex on one side connects to every vertex on the other side) These graphs are fundamentally non-planar—they cannot be drawn without edge crossings. Moreover, they characterize all non-planar graphs. Wagner's theorem states: A graph is planar if and only if it does not contain $K5$ or $K{3,3}$ as a minor. A minor of a graph is obtained by deleting vertices/edges and contracting edges (merging two adjacent vertices into one). Kuratowski's theorem is a related result: A graph is planar if and only if it does not contain $K5$ or $K{3,3}$ as a subdivision. A subdivision is obtained by deleting edges and inserting new vertices along existing edges—it's a less aggressive operation than taking a minor. Both theorems are ways of saying: "If your graph contains the 'forbidden structures' $K5$ or $K{3,3}$ (in these specific senses), then it cannot be drawn planarly." Fundamental Graph Problems Graph theory poses many natural questions. Some of these can be solved efficiently with known algorithms, but others are computationally hard (NP-complete). Understanding which problems are hard is crucial for knowing when to expect a quick solution versus when you need approximations or heuristics. Graph Isomorphism The graph isomorphism problem asks: are these two graphs "the same" up to relabeling of vertices? More formally, two graphs $G$ and $H$ are isomorphic if there exists a relabeling (bijection) of the vertices of one graph that makes it identical to the other. Example: These two drawings represent isomorphic graphs—they have the same connectivity structure, just drawn differently: Graph 1: Graph 2: 1 — 2 A — B | | | | 4 — 3 D — C Both graphs are 4-cycles with the same edge structure. By relabeling 1→A, 2→B, 3→C, 4→D, they become identical. Why does isomorphism matter? In chemistry, molecular graphs are isomorphic if they represent the same compound. In networks, isomorphic subgraphs represent the same structural pattern. However, the complexity of graph isomorphism is unknown—it's not known whether there's a polynomial-time algorithm, and it's not known to be NP-complete. This makes it one of the most famous open problems in computer science. Subgraph Isomorphism and the Clique Problem The subgraph isomorphism problem generalizes graph isomorphism: does a fixed graph $G$ appear as a subgraph of a larger graph $H$? That is, can you find a copy of $G$ "hiding inside" $H$ by relabeling vertices? A special case is the clique problem. A clique is a subset of vertices where every pair is connected by an edge—it's a complete subgraph. The maximum clique problem asks: what is the largest clique in this graph? Example: In a friendship network, a clique represents a group of people who are all friends with each other. Finding the largest clique is an NP-complete problem, meaning there's no known polynomial-time algorithm for it. The Independent Set Problem An independent set is a set of vertices where no two are adjacent—the opposite of a clique. The independent set problem asks: what is the largest independent set in this graph? Example: In a scheduling problem, vertices represent tasks and edges connect tasks that conflict (can't be done simultaneously). An independent set represents tasks that don't conflict and can all be scheduled at once. Like the clique problem, the maximum independent set problem is NP-complete. In fact, finding the maximum independent set in a graph is equivalent to finding the maximum clique in the complement graph (the graph where edges are reversed). Graph Enumeration Graph enumeration counts how many graphs with specified properties exist. For instance: "How many non-isomorphic graphs are there with exactly 5 vertices and 7 edges?" While enumeration is important theoretically and useful for testing algorithms, it's rarely a focus of algorithmic study on exams unless specifically emphasized in your course. <extrainfo> Enumeration problems are more combinatorial and less algorithmic than other graph problems. Unless your course explicitly covers enumeration, this is likely secondary material. </extrainfo> Graph Coloring Vertex Coloring Fundamentals Vertex coloring assigns colors (usually represented as numbers) to the vertices of a graph such that adjacent vertices always receive different colors. The chromatic number of a graph is the minimum number of colors needed. Example: A bipartite graph (a graph whose vertices can be split into two groups with edges only between groups, never within) requires exactly 2 colors. One group gets color 1, the other gets color 2, and no adjacent vertices share a color. Computing the chromatic number is NP-hard, but determining the chromatic number for specific graph classes can be straightforward. For instance: Trees always have chromatic number 2 (they're bipartite) A complete graph $Kn$ has chromatic number $n$ (every vertex is adjacent to every other) A cycle has chromatic number 2 if it has even length, and 3 if it has odd length The Four-Color Theorem One of the most famous theorems in mathematics is the four-color theorem: any planar graph has chromatic number at most 4. This means you can color any map with at most 4 colors such that neighboring regions always have different colors. The theorem was historically important because it was one of the first major theorems proved by computer (in 1976), relying on computational verification of thousands of cases. The intuition is that planarity (being drawable without crossings) severely restricts a graph's structure, preventing it from needing many colors. However, the proof is surprisingly difficult and requires computational assistance. <extrainfo> The four-color theorem is famous and important, but unless your course focuses on graph coloring or planar graph theory specifically, you mostly need to know it exists and what it says, not the proof (which is beyond the scope of most courses anyway). </extrainfo> Strong Perfect Graph Theorem <extrainfo> A perfect graph is one where the chromatic number and maximum clique size are equal for every induced subgraph. The strong perfect graph theorem characterizes perfect graphs: they are exactly those graphs containing no induced odd cycle of length ≥ 5 and no induced complement of such a cycle. This is a beautiful characterization but typically appears only in advanced graph theory courses. It's likely not essential for most exams unless coloring or perfect graphs are a major focus. </extrainfo> Graph Classes and Recognition Different graphs have different properties. A graph class is a set of graphs sharing some common property: all planar graphs, all bipartite graphs, all trees, etc. An important algorithmic question is: can we efficiently recognize whether a given graph belongs to a specific class? Efficient Recognition Algorithms Fortunately, many important graph classes can be recognized in polynomial time: Planarity testing can be done in linear time $O(|V| + |E|)$ using algorithms like Hopcroft-Tarjan Bipartiteness testing is trivial: a graph is bipartite if and only if it has no odd cycles, which can be checked by trying to 2-color the graph (linear time) Chordality testing determines if a graph is chordal (every cycle of length 4 or more has a chord—an edge connecting non-consecutive vertices in the cycle). This can be done in polynomial time. These efficient algorithms are practical tools: if you need to verify that a graph has a certain property, you can often do so quickly. Relationships Among Graph Classes Understanding how graph classes relate to each other is important for reasoning about graph properties. Key inclusion relationships: Every tree is bipartite (trees have no cycles, so certainly no odd cycles) Every bipartite graph is 2-colorable (by definition—the two parts get different colors) Every planar graph is 4-colorable (by the four-color theorem) Every tree is planar (trees can be drawn without crossings) These relationships mean that if you know a graph is a tree, you automatically know it's bipartite, 2-colorable, and planar. These properties "propagate downward" through the class hierarchy. Understanding these relationships helps you quickly deduce properties of graphs without recomputing them. Summary Graph representations determine how efficiently you can perform operations: lists are flexible for traversal, while matrices enable algebraic methods. The fundamental graph problems—isomorphism, cliques, independent sets, coloring—define the landscape of what's computationally tractable. Planarity is a special property with clean characterizations (Wagner and Kuratowski), and specific graph classes can often be recognized in polynomial time. Together, these concepts form the foundation for reasoning about and working with graphs algorithmically.