Graph Theory Blog
Deep-dive articles, intuitive explanations, and real-world applications of Graph Theory and Software Engineering concepts.
Strongly Connected Components: Tarjan and Kosaraju
Tarjan's low-links, Kosaraju's two passes and the path-based method traced on one digraph, the bugs that pass small tests, and SCCs at work in 2-SAT and the web's bow-tie.
Capital Budgeting: Choosing Projects When You Can't Fund Them All
Fourteen projects, $10 million: why ranking by profitability index left $910,000 on the table, and why the best portfolio funds a project that loses money.
Assigning Work Fairly and Cheaply: The Hungarian Algorithm
Technicians, drivers and nurses assigned exactly: why dispatching in booking order cost 132 extra minutes a day, and when the best plan is not stable.
Inventory Optimization: How Much Stock Should You Hold?
One distributor, seven stocking decisions: supplier delays drove 77% of the risk, and the same 98% fill rate needed 34% less safety stock.
Network Design: Minimum Cost, Maximum Reliability
One fibre region designed seven ways: why the cheapest tree cost $271,383 a year more than the best design, and when a full ring pays.
Production Scheduling: From Spreadsheets to Optimization
Eight orders on one line, sequenced seven ways: why the spreadsheet order cost $7,750 more in a week, and how to price a rush order.
Facility Location: Where to Put Your Next Warehouse
Four siting methods against a proven optimum: why the centre of gravity cost $114,880 a year, and what losing one warehouse really costs.
Employee Shift Scheduling
One week rostered five ways and priced: why the costliest roster covered every shift, when to hire, and what two days off really cost.
Delivery Route Optimization
One delivery day planned five ways and priced: why the best plan saved a van rather than kilometres, and what a delivery window really costs.
Max-Flow & Min-Cut Interview Questions
Bipartite matching, Konig, recovering the cut, disjoint paths, project selection and baseball elimination, all on one small network.
Graph Theory in Project Management
Critical path, float, PERT probabilities, the merge bias, crashing as a minimum cut, and what a resource limit really costs you.
Graph Theory in Biology
Protein hubs, network motifs, genome assembly as an Eulerian path, phylogenetic trees, and the food web species whose loss brings down everything else.
Graph Theory in Cybersecurity
Attack paths, the host that carries the most routes, the cheapest set of controls that breaks every path, blast radius, and the threshold that decides an outbreak.
Graph Theory in Supply Chain Optimization
One four-echelon network solved six ways: lead times, throughput and bottlenecks, the cheapest plan, which warehouses to open, and what a failure really costs.
Union-Find Interview Questions
Eight union-find questions worked end to end: components, redundant connection, islands II, accounts merge, stones, weighted DSU and Kruskal.
Topological Sort Interview Questions
Eight topological sort questions worked end to end: course schedule, alien dictionary, parallel courses, unique orders, critical paths and safe states.
Introduction to Graph Theory
A complete first course in one page: the definition, the vocabulary, the families of graphs, traversal, the classic problems and theorems, and what is easy or hard to compute.
Graph Algorithms Complexity: The Ultimate Guide
A comprehensive deep dive into the time and space complexity of all major graph algorithms. Learn Big O notation for BFS, DFS, Dijkstra, A*, Kruskal, and more.
Kruskal's MST Algorithm Explained
The cycle property that makes rejecting an edge provably safe, a worked six-vertex trace, why union-find is the engine, and how it compares with Prim's.
Prim's MST Algorithm Explained
The cut property that makes the greedy choice provably safe, a worked six-vertex trace, lazy versus eager implementations, and the single line separating it from Dijkstra's.
Floyd-Warshall Algorithm Explained
All-pairs shortest paths in three nested loops: the dynamic programming recurrence, a worked matrix trace, free negative cycle detection, and when it beats repeating Dijkstra.
Vertices and Edges Explained
Start here. The formal definition of a graph, adjacency and incidence, degree and the handshaking lemma, with references to the standard texts.
Directed vs Undirected Graphs Explained
Ordered pairs against unordered ones: in-degree and out-degree, matrix symmetry, orientations and Robbins theorem, and which algorithms stop working.
Weighted vs Unweighted Graphs Explained
Fewest edges is not least cost. How weights combine, which algorithm each kind forces on you, and the exact point where Dijkstra stops being correct.
Simple Graphs vs Multigraphs Explained
Loops and parallel edges: what multiplicity changes, which standard bounds stop holding, and why the founding problem of the subject cannot be a simple graph.
Finite and Infinite Graphs Explained
What finiteness was quietly buying you: which standard proofs collapse without it, and the compactness theorems that carry facts across to infinity anyway.
Bipartite Graphs Explained
Two colours and every edge between them: the odd-cycle theorem, a linear-time test that hands back proof either way, and the matching theory built on top.
Planar Graphs and Euler's Formula
Which graphs can be drawn without crossings: faces, Euler's formula with proof, the edge bounds that rule out K₅ and K₃,₃, Kuratowski's theorem and the four colour theorem.
Connected Components, Bridges and Articulation Points
When a graph holds together and how firmly: counting components, the edges and vertices it cannot lose, and the one depth-first search that finds them all.
Cycles in Graphs and Cycle Detection
What a cycle is, how to detect one in directed and undirected graphs and return it as proof, and how the cycle space counts them all.
Vertex Degree and the Handshaking Lemma
The simplest number in graph theory: the handshaking lemma and the puzzles it settles, graphic degree sequences, what degree bounds guarantee, k-cores and the friendship paradox.
Trees in Graph Theory
Seven equivalent definitions, the leaf lemma, Cayley’s formula and the Prüfer bijection, spanning trees, and finding a centre in linear time.
Graph Representation
Edge list, adjacency matrix, adjacency list and CSR compared on space and query cost, plus the density crossover that decides between them.
BFS Interview Questions
Eight recurring BFS problems worked end to end, each with the follow-up the interviewer asks next and the mistake that loses the offer.
DFS Interview Questions
Eight recurring DFS problems worked end to end, from three-colour cycle detection to bridges and low-link, each with its follow-up and its trap.
Dijkstra Interview Questions
Eight recurring Dijkstra problems worked end to end, from lazy deletion to minimax paths and counting, each with its follow-up and its trap.
BFS vs DFS: The Ultimate Guide to Graph Traversal
A comprehensive comparison between Breadth-First Search and Depth-First Search. Learn when to use each algorithm with real-world examples.
Understanding Shortest Path Algorithms
Master Dijkstra, Bellman-Ford, and Floyd-Warshall. Understand the nuances of finding the fastest route in complex networks.
The Magic of Minimum Spanning Trees
Dive into Kruskal's and Prim's algorithms. Learn how to connect networks with the absolute minimum cost.
Top 5 Real-World Applications of Graph Theory
From Google Maps to Social Networks and DNA sequencing. Discover how graph theory powers the modern world.
Essential Graph Algorithms for Coding Interviews
Crack the technical interview. A curated guide to the graph theory concepts you absolutely must know for FAANG interviews.
The Traveling Salesperson Problem (TSP)
Explore one of computer science's most famous unsolved problems. Learn about heuristics, exact algorithms, and its vast applications.
The Vehicle Routing Problem (VRP)
How Amazon and FedEx deliver packages. A deep dive into the algorithms powering modern logistics and supply chains.
A* Search Algorithm: Pathfinding in AI
The gold standard for pathfinding in video games and robotics. Learn how heuristics make A* vastly superior to standard Dijkstra.
A* Search Algorithm in AI: The Complete Guide
f = g + h from first principles: the 1968 paper, admissible and consistent heuristics, the optimality proof, complexity and variants.
The Graph Coloring Problem: From Maps to Sudoku
How do you schedule exams without conflicts? Discover how coloring graphs solves complex allocation and scheduling problems.
Practical Software Engineering Concepts
See how Graph Theory underpins build systems, garbage collection, version control (Git), and database deadlocks.
Network Flow and The Max-Flow Min-Cut Theorem
Understand Ford-Fulkerson, Edmonds-Karp, residual graphs, and the beautiful symmetry between finding max flow and minimum cuts.
The History of Graph Theory
From Königsberg to Neural Networks. Discover the fascinating history of graph theory, from Euler's Seven Bridges to modern network science.
Top Graph Theory Interview Questions & Solutions
Master the technical interview with our guide to the most common graph theory questions, from Number of Islands to Topological Sort.
Eulerian Paths and Circuits
Can you cross every bridge exactly once? Euler's 1736 answer launched graph theory. Learn the odd-degree rule plus Fleury's and Hierholzer's algorithms.
Rooted Trees in Graph Theory
Root, parent, child, leaf, depth and height, plus binary trees, BSTs and DFS/BFS traversal. The hierarchy behind file systems and the DOM.
Spectral Graph Theory in Machine Learning
The graph Laplacian, eigenvalues and the Fiedler vector, spectral clustering, Laplacian eigenmaps and spectral GNNs (ChebNet, GCN), the linear algebra behind modern ML on graphs.
Graph Neural Networks: A Practical Introduction
Message passing and neighbourhood aggregation, how a GNN layer works, the GCN, GraphSAGE, GAT and GIN architectures, the three prediction tasks, and real-world applications.
What Is Operations Research? Methods & Applications
The science of better decisions. Its wartime history, core methods like linear programming and simulation, and how OR optimizes logistics, airlines, healthcare, and energy.
Graph Theory Study Roadmap
Learn graph theory in the right order. Seven stages that take you from vertices and edges to shortest paths, network flow, and interview-ready mastery.
Graph Algorithms Cheat Sheet
One page to scan before an interview. Time and space complexity for every major graph algorithm, what each is best for, and a decision guide for picking the right one.
Dijkstra's Algorithm Explained
How Dijkstra finds the shortest path in a weighted graph, built up from the core idea to a full worked example, Python code, complexity, and when it fails.
Topological Sort Explained
How topological sort orders a DAG by dependencies. Kahn's algorithm and the DFS approach, a worked example, Python code, and how it detects cycles.
Union-Find (Disjoint Set) Explained
How the union-find data structure tracks disjoint sets in near-constant time: find and union, path compression, union by rank, Python code, and where it powers Kruskal and cycle detection.
Chordal Graphs Explained
What chordal graphs are, chords and induced cycles, simplicial vertices and perfect elimination orderings, linear-time recognition, and why hard problems become easy.
The Best Resources to Learn Graph Theory
A curated guide to the best books, courses, video series, interactive tools, and practice sites for learning graph theory, matched to your goal and level.
Bellman-Ford Algorithm Explained
How Bellman-Ford finds shortest paths when edges are negative, detects negative cycles, and powers routing and arbitrage, with edge relaxation, pseudocode, and complexity.