Introduction to Graph Theory

Graph Theory: Definitions and Basic Properties Introduction Graphs are one of the most important data structures in computer science and mathematics. A graph provides a way to represent relationships or connections between objects. Whether you're modeling social networks, transportation systems, web pages, or molecules, graphs offer a unified framework. This guide covers the fundamental definitions and properties of graphs that form the foundation for all graph-based problems you'll encounter. Definitions of Graphs The Basic Components A graph is a mathematical structure consisting of two key components: Vertices (also called nodes) are the fundamental units of a graph. Think of them as points or objects. In practical applications, vertices might represent cities, people, computers, or any entities you want to model. Edges are connections between vertices. An edge links a pair of vertices together, representing a relationship or connection between them. Types of Graphs: Directed vs. Undirected The distinction between undirected graphs and directed graphs is crucial and affects how we interpret the relationships in the graph. In an undirected graph, edges have no direction. If there's an edge between vertex A and vertex B, the connection works both ways—you can think of it as a two-way relationship. These edges are represented as unordered pairs of vertices. Undirected graphs are useful for modeling relationships like friendships (if A is friends with B, then B is friends with A) or roads connecting cities (you can travel in both directions). In a directed graph (or digraph), edges point from one vertex to another, representing one-way relationships. Each edge has a tail (the origin vertex) and a head (the destination vertex). An arrow shows the direction of the edge. Directed graphs are useful for modeling things like web links (a webpage links to another), Twitter follows (A follows B, but B might not follow A), or task dependencies (task A must be completed before task B). Simple Graphs A simple graph has two important restrictions: It contains no loops: a loop is an edge that connects a vertex to itself. This doesn't make sense in many practical scenarios. It contains no multiple edges: there is at most one edge between any pair of vertices. You either have a connection or you don't. Unless stated otherwise, assume you're working with simple graphs. Basic Notions Vertex Degree The degree of a vertex measures how many connections it has. The specific definition depends on whether your graph is directed or undirected. In an undirected graph, the degree of a vertex is simply the count of edges connected to it. For example, if vertex A has edges to B, C, and D, then the degree of A is 3. Degree tells you how "popular" or "connected" a vertex is in the network. In a directed graph, we distinguish between two types of degree: In-degree counts the number of edges arriving at (pointing to) a vertex Out-degree counts the number of edges leaving (pointing from) a vertex For example, if vertex A has edges coming in from B and C, and edges going out to D and E, then A has in-degree 2 and out-degree 2. A useful fact: in any directed graph, the sum of all in-degrees equals the sum of all out-degrees, which both equal the total number of edges. Paths and Cycles A path is a sequence of edges that connects vertices without repeating any edge. Think of a path as a route through the graph. A path from vertex A to vertex B shows you can "travel" from A to B following the edges of the graph. The length of a path is the number of edges it contains. A cycle is a special kind of path: it's a closed path that starts and ends at the same vertex, without repeating any edges. Cycles are important because they represent the possibility of returning to where you started. For example, in a social network, a cycle might represent a chain of introductions that leads back to the original person. A key distinction: a simple path doesn't repeat vertices (except possibly the start and end), while a simple cycle is a closed simple path. Connectivity A graph is connected if there is a path between every pair of vertices. In other words, you can travel from any vertex to any other vertex by following the edges. This is an important property—a disconnected graph breaks into separate pieces where some vertices cannot reach others. For directed graphs, there's a related concept: a directed graph is strongly connected if there's a directed path from every vertex to every other vertex. Trees: A Special Case A tree is one of the most important graph structures. A tree is defined as a connected graph that contains no cycles. Trees are acyclic, meaning you can never return to the starting point by following edges without backtracking. Trees have a special property: a tree with $n$ vertices has exactly $n - 1$ edges. This relationship is fundamental and often used to verify whether a connected graph is a tree. For example: A tree with 4 vertices must have exactly 3 edges A tree with 10 vertices must have exactly 9 edges This makes sense intuitively: each edge beyond $n-1$ would create a cycle, breaking the tree property. Special Families of Graphs Bipartite Graphs A bipartite graph has a special structure: its vertices can be divided into two disjoint sets (call them Set A and Set B) such that every edge connects a vertex in Set A to a vertex in Set B. No edges exist within Set A, and no edges exist within Set B—all connections go between the two sets. Bipartite graphs model many real-world scenarios: students and courses (edges represent enrollment), employers and job candidates (edges represent applications), or actors and movies (edges represent appearances). Key property: A graph is bipartite if and only if it contains no odd-length cycles. This means any cycle in a bipartite graph must have an even number of edges. This property gives you a way to check if a graph is bipartite: if you ever find a cycle of odd length, the graph is not bipartite. Planar Graphs A planar graph can be drawn on a flat sheet of paper without any edges crossing each other. This is a geometric property—it's about how you can visualize the graph, not about the abstract structure itself. Note that the same graph can be drawn in different ways; what matters is whether some way of drawing it exists without crossings. Planar graphs are important in circuit design, map coloring, and many other applications. Euler's Formula is a fundamental result for connected planar graphs: $$V - E + F = 2$$ where: $V$ = number of vertices $E$ = number of edges $F$ = number of faces (regions created by the drawing, including the outer infinite region) This formula beautifully connects the combinatorial structure (vertices and edges) with the geometric property (faces). Example: A simple planar graph—a triangle—has 3 vertices, 3 edges, and 2 faces (inside and outside). Check: $3 - 3 + 2 = 2$ ✓ Constraints on Planar Graphs Not all graphs can be drawn without crossings. Planar graphs must satisfy certain inequality constraints. For planar graphs with $V \geq 3$ vertices, the following inequality must hold: $$E \leq 3V - 6$$ This is a necessary condition: if a graph violates this inequality, it cannot be planar. However, satisfying this inequality doesn't guarantee planarity—a graph could satisfy the bound and still be non-planar. This inequality tells us that planar graphs cannot have too many edges relative to their vertices. The more vertices you have, the more edges you can add, but always within this bound.