1 Introduction: Modeling Connections and Networks
Look around the physical and digital world, and you will find that almost everything is an interconnected web:
- Social Networks: Billions of users interconnected via friendship, follows, and interactions.
- Transportation & Logistics: Cities and intersections connected by roads, flight paths, and shipping lanes.
- The World Wide Web: Billions of HTML web pages interconnected by directional hyperlinks.
- Computer Networks: Data centers, routers, switches, and client devices exchanging packets over fiber and wireless links.
The mathematical discipline dedicated to formalizing, analyzing, and optimizing these relationship structures is Graph Theory.
Core Definitions: Graphs and Trees
A Graph is a mathematical structure consisting of discrete entities called Vertices (or Nodes) and the connections between them called Edges.
A Tree is a specialized, cycle-free (acyclic) connected graph that organizes elements into a strictly hierarchical structure with uniquely determined paths.
2 Formal Definition of a Graph
Formally, a graph \(G\) is defined as an ordered pair of sets:
where:
- \(V\) (Vertex Set): A non-empty, finite set of vertices or nodes.
- \(E\) (Edge Set): A set of edges, where each edge connects a pair of vertices from \(V\).
Concrete Example: A 4-Node Local Network
Consider four computers \(A, B, C, D\) connected by ethernet cables:
Key Insight: In graph theory, physical geometric properties like node placement, line length, or visual shapes are irrelevant. Only the underlying topology—which node is connected to which—matters.
3 Vertices and Edges
The fundamental building blocks of all graph architectures:
Represents a distinct entity, state, or point in the system.
Real-world instances: A user in a social network, a city or intersection on a map, a router in a subnet, a web page.
Represents a relationship, physical channel, or dependency between two vertices.
Real-world instances: Mutual friendship, a highway connection, a directional hyperlink, a wired network link.
4 Classifications and Types of Graphs
Graphs are classified based on directionality, edge weights, and structural constraints:
4.1 Undirected Graph
Bidirectional Symmetry
Edges have no direction. An edge \(\{A, B\}\) implies that travel or communication is symmetric between \(A\) and \(B\).
Applications: Facebook friendships, bidirectional roads, peer-to-peer file sharing networks.
4.2 Directed Graph (Digraph)
Ordered Arcs
Edges are ordered pairs \((u, v)\) represented with directional arrows. An edge from \(u \to v\) does not imply a return path from \(v \to u\).
Applications: Twitter/X follower relationships, web hyperlinks, software package build dependencies (Directed Acyclic Graphs / DAGs).
4.3 Weighted Graph
Numerical Weights
Each edge carries a numerical weight \(w(e)\) reflecting physical distance, latency, toll costs, or inverse bandwidth.
Example: In road networks, distance from city \(A\) to \(B\) is 10 km, while \(B\) to \(C\) is 20 km. Total path weight \(A \to B \to C = 30\) km vs. direct \(A \to C = 40\) km.
4.4 Simple Graph
Loop-free & Single-edgeAn undirected graph containing no self-loops (edges connecting a node to itself) and no parallel edges (multiple edges between the same pair of nodes). Unless specified otherwise, discrete mathematics typically studies simple graphs.
4.5 Complete Graph (\(K_n\))
Maximal Connectivity
A simple graph where an edge exists between every distinct pair of vertices. A complete graph on \(n\) vertices is denoted \(K_n\).
Total edges in \(K_n\):
\(|E| = \binom{n}{2} = \frac{n(n-1)}{2}\)
Examples: \(K_3\) has 3 edges; \(K_4\) has 6 edges; \(K_5\) has 10 edges.
5 Degree of a Vertex & The Handshaking Lemma
In an undirected graph, the Degree of a vertex \(v\), denoted \(\deg(v)\), is the number of edges incident to it.
Special Vertex Categories:
- Isolated Vertex: A vertex with degree zero (\(\deg(v) = 0\)). It possesses no edges.
- Pendant / Leaf Vertex: A vertex with degree one (\(\deg(v) = 1\)). It represents an endpoint in the graph.
The Handshaking Lemma
In any undirected graph, the sum of the degrees of all vertices equals exactly twice the total number of edges:
Proof Intuition: Every edge has exactly two endpoints. Therefore, each edge contributes \(+1\) to the degree of each incident vertex, adding \(+2\) to the total degree sum. (Just as each handshake at a party involves two people, doubling the total hand count).
6 Directed Graphs: In-degree and Out-degree
Because directed edges possess orientation, vertex degrees are split into incoming and outgoing directions:
- In-degree (\(\deg^-(v)\)): Number of directed edges entering vertex \(v\).
- Out-degree (\(\deg^+(v)\)): Number of directed edges leaving vertex \(v\).
The sum of in-degrees equals the sum of out-degrees, both equaling the total number of directed edges. Google\'s PageRank algorithm evaluates web page importance by modeling random web surfers traversing in-degree and out-degree transitions.
7 Walks, Trails, Paths, and Cycles
Graph traversal terminology must be precisely distinguished:
| Concept | Definition | Repetition Constraints |
|---|---|---|
| Walk | Any sequence of adjacent vertices and edges | Vertices and edges may repeat arbitrarily |
| Trail | A walk with no repeated edges | Edges must be unique; vertices may repeat |
| Path (Simple Path) | A walk with no repeated vertices | No vertex (and hence no edge) may repeat |
| Cycle | A closed simple path starting and ending at the same node (\(A \to B \to C \to A\)) | Only initial and final vertices coincide |
8 Connected Graphs and Connected Components
An undirected graph is Connected if there exists at least one simple path between every pair of vertices.
If there exist isolated nodes or islands between which no path can be traced, the graph is Disconnected.
Connected Components
A disconnected graph can be decomposed into disjoint maximal connected subgraphs called Connected Components. Graph search algorithms (BFS and DFS) are routinely deployed to discover cluster groupings and segment disconnected subnetworks.
9 Graph Representation in Computer Memory
Two dominant data structures represent graphs in computer memory:
A \(|V| \times |V|\) 2D array where \(M[i][j] = 1\) if an edge exists, and \(0\) otherwise.
A B C D A [0 1 1 0] B [1 0 1 0] C [1 1 0 1] D [0 0 1 0]
- Space: \(O(V^2)\)
- Edge Lookup: \(O(1)\) (Instantaneous)
- Best for: Dense graphs (\(|E| \approx |V|^2\)).
An array or hash map storing a dynamic list of directly connected neighbor nodes for each vertex.
A: [B, C] B: [A, C] C: [A, B, D] D: [C]
- Space: \(O(V + E)\) (Highly Memory-Efficient)
- Edge Lookup: \(O(\deg(v))\)
- Best for: Sparse graphs (99% of real-world networks).
10 Graph Traversal: BFS vs. DFS
The two canonical algorithmic approaches for visiting all vertices in a graph:
Breadth-First Search (BFS)
Queue (FIFO)
Visits all immediate neighbors at the current level before expanding outward to nodes at distance 2, 3, and beyond.
Primary Application: Finding the Shortest Path in unweighted graphs. Time: \(O(V + E)\).
Depth-First Search (DFS)
Stack / Recursion
Explores as deeply as possible along a single branch before backtracking to explore alternate branches.
Primary Application: Cycle detection, topological sorting, maze solving. Time: \(O(V + E)\).
11 Shortest Path vs. Minimum Spanning Tree
Two fundamental graph optimization problems with distinctly different goals:
1. Shortest Path (Dijkstra's Algorithm)
Finds the path between a specific source node and destination node with the minimum cumulative edge weight. Deployed in GPS navigation, network packet routing protocols (OSPF), and game AI.
2. Minimum Spanning Tree (MST — Kruskal & Prim)
Finds a cycle-free subset of edges that connects every vertex in the graph while minimizing the total sum of edge weights.
Core Difference: Shortest path minimizes cost between two specific points; MST connects the entire network with minimum total wiring cost.
12 Formal Definition of a Tree
Mathematically, a Tree is an undirected graph that is both Connected and Acyclic.
Golden Mathematical Properties of Trees:
In any tree containing \(n\) vertices, the number of edges is always strictly:
• There exists exactly one unique simple path between any two distinct vertices in a tree.
• Adding any new edge to a tree produces exactly one cycle.
• Removing any edge disconnects the tree (every edge is a bridge).
13 Rooted Trees and Hierarchical Terminology
In computer science, trees are traditionally drawn inverted, with the Root at the top branching downwards:
The topmost node of the tree, possessing no parent. All downward paths originate here.
A node directly above is the Parent; nodes directly below connected by edges are its Children.
A node with zero children (degree 1, connected only to its parent). Also termed External Nodes.
Depth: Number of edges from the root down to the node.
Height: Number of edges on the longest downward path from the node to a leaf.
14 Binary Trees and Binary Search Trees (BST)
A Binary Tree is a rooted tree in which each node has at most two children (designated as the Left Child and Right Child).
The Binary Search Tree (BST) Ordering Invariant:
For every node in a BST, values are partitioned symmetrically:
Because of this ordering, each comparison halves the search space. In a balanced BST (AVL or Red-Black Tree), search, insertion, and deletion execute in logarithmic time: \(O(\log n)\).
15 Tree Traversals
Four standardized algorithms for visiting all nodes in a binary tree:
| Traversal Type | Visitation Rule | Primary Use Case |
|---|---|---|
| Preorder | Root → Left → Right | Cloning tree structures and prefix expression parsing |
| Inorder | Left → Root → Right | Retrieves elements of a BST in strictly sorted ascending order! |
| Postorder | Left → Right → Root | Deleting trees and directory size calculations |
| Level-Order | Level-by-level (BFS Queue) | Layer-by-layer printing and breadth-wise rendering |
16 Tree vs. General Graph Comparison
| Characteristic | General Graph | Tree |
|---|---|---|
| Cycles | May contain cycles | Strictly Acyclic (No cycles) |
| Connectivity | May be connected or disconnected | Always 100% Connected |
| Edge Count (\(|E|\)) | Arbitrary (\(0\) to \(\binom{n}{2}\)) | Exactly \(n - 1\) |
| Paths Between Nodes | Zero, one, or multiple paths | Exactly one unique simple path |
| Hierarchy | No root or hierarchy required | Explicit Parent-Child hierarchy when rooted |
17 Real-World Applications in Computer Science and AI
Internet core routers deploy Dijkstra and Bellman-Ford algorithms to route packets along the lowest latency paths.
Mutual friend recommendations, community detection, and influencer ranking algorithms leverage graph centrality metrics.
Relational engines like MySQL and PostgreSQL utilize B-Trees to execute range queries across millions of records in milliseconds.
Random Forest and XGBoost machine learning architectures make predictions by ensembling thousands of decision tree branches.
Google Search and Wikidata model interconnected world entities as knowledge graphs to power conversational AI systems.
Compilers parse source code into Abstract Syntax Trees (ASTs) to evaluate grammar, optimize bytecode, and generate machine instructions.
18 9 Common Pitfalls in Graph Theory and Trees
Vertices are objects (nouns); edges are the connecting relations (verbs).
Degree is local to a single node. Total degree sum is always double the total edge count (\(2|E|\)).
Walks permit repeated vertices and edges. Paths strictly forbid repeated vertices.
Connectivity alone is insufficient; a tree must also be strictly acyclic.
Shortest path minimizes cost between two specific endpoints; MST minimizes total edge cost across the entire graph.
In a binary tree, nodes have at most 2 children (0, 1, or 2).
Depth measures downward from the root; height measures upward from the deepest descendant leaf.
BFS explores level-by-level via a queue; DFS dives deep along single branches via recursion.
Graph Theory & Trees Workbench
Live simulators for the Handshaking Lemma, BFS/DFS traversal, and Binary Search Trees
20 Key Takeaways
G = (V, E). Vertices represent entities; edges represent connecting relations.
Total degrees equal twice the edge count (∑ deg(v) = 2|E|). Odd degree nodes always occur in even counts.
Total in-degrees equal total out-degrees, both equaling the total number of directed edges.
Walks permit repeated nodes and edges. Simple paths strictly forbid any vertex repetition.
Memory O(V + E) for sparse graphs. Far more space-efficient than matrices for real-world networks.
BFS explores levels via a queue (shortest path); DFS explores branch depth via recursion/stack.
Connected and strictly acyclic. An n-node tree possesses exactly n - 1 edges with unique paths.
Left < Root < Right. An inorder traversal produces keys in strictly sorted numerical order.
Part 2 completed! Next, we transition into Part 3: Linear Algebra with Scalars and Vectors.