Hypercube Q3 (3D Cube)
The hypercube Q3 = Q2 square K2. Eight vertices labeled with 3-bit binary strings. Two vertices are…
Last modified: Jul 14, 2026
Hypercube Q2 (2D Square)
The hypercube Q2 = K2 square K2. Four vertices labeled with 2-bit binary strings: 00, 01, 10, 11. T…
Last modified: Jul 14, 2026
Grid Graph P4 square P3 (Cartesian Product)
The Cartesian product P4 square P3: a 4x3 rectangular grid with 12 vertices labeled (vi,wj). Horizo…
Last modified: Jul 14, 2026
Path P3 (for Cartesian Product)
The path graph P3 with vertices w1-w2-w3. Used as the second factor in the Cartesian product P4 squ…
Last modified: Jul 14, 2026
Path P4 (for Cartesian Product)
The path graph P4 with vertices v1-v2-v3-v4. Used as one factor in the Cartesian product P4 square …
Last modified: Jul 14, 2026
Line Graph L(G) of the Previous Graph
The line graph L(G) built from gop-line-g. Each edge of G becomes a colored vertex: orange=e1:AB, t…
Last modified: Jul 14, 2026
Graph G (for Line Graph Construction)
Original graph G with 4 vertices {A,B,C,D} and 5 edges {AB, BC, CD, AC, BD}. Each edge is labeled a…
Last modified: Jul 14, 2026
Join K1 v C5 = Wheel Graph W5
The join of K1 (orange hub vertex H) and C5 (teal ring vertices A-E). Every ring vertex gets a spok…
Last modified: Jul 14, 2026
Union G cup H: Triangle and Square
The union of K3 (orange triangle, vertices A/B/C) and C4 (teal square, vertices D/E/F/G). The two c…
Last modified: Jul 14, 2026
Graph G-bar (Complement of G)
The complement G-bar of the previous graph. Same 5 vertices, but now every former non-edge (teal) i…
Last modified: Jul 14, 2026
Graph G (for Complement Example)
Original graph G with 5 vertices {A,B,C,D,E} and 5 edges (orange). Used to demonstrate the compleme…
Last modified: Jul 14, 2026
Bridge Splits Into Exactly Two Components
A connected graph with bridge B-C (red). Removing it creates exactly two components: {A,B} shown in…
Last modified: Jul 12, 2026
Distance in a Graph
The base 5-vertex graph with distances from A labeled on nodes: d(A,A)=0, d(A,B)=1, d(A,C)=1, d(A,D…
Last modified: Jul 12, 2026
Cycle Example — C₅ (Closed, No Repeated Vertices)
A 5-cycle C5: A→B→C→D→E→A. Every vertex except the start/end is visited exactly once. Every edge is…
Last modified: Jul 12, 2026
Walk Example: A → B → D → C → A (Closed Walk)
Closed walk of length 4 tracing the square A-B-D-C-A. All four edges of the square are highlighted …
Last modified: Jul 12, 2026
Walk Example: C → D → C → A (Repeated Edge)
Walk of length 3 where edge C-D is traversed twice (once forward, once back). Orange highlights sho…
Last modified: Jul 12, 2026
Walk Base Graph — Neighbourhood
The base graph used in the Walks in Graphs post. Vertices A–E form a small neighbourhood: A-B acros…
Last modified: Jul 12, 2026
Simple Tree (Enhanced Layout)
Rooted binary tree — Root -> Left/Right -> LL/LR/RL. 6 nodes, 5 edges.
Last modified: Jul 12, 2026
Bipartite Graph - Job Applicants (Enhanced)
Applicants (Alice, Bob, Carol) matched to jobs (Developer, Designer, Manager). Colour-coded nodes.
Last modified: Jul 12, 2026
Complete Graph K4 (Enhanced Layout)
K4 in diamond layout (V1 top, V2 right, V3 bottom, V4 left). Cleaner for blog embeds.
Last modified: Jul 12, 2026
Independent Set — No Two Members are Adjacent
A graph with 7 vertices. The orange nodes {A, C, F} form a maximum independent set — no edge connec…
Last modified: Jul 11, 2026
Clique — K4 Hiding Inside a Larger Graph
A graph with 7 vertices. The green nodes {A, B, C, D} and green edges form a 4-clique (K4 subgraph)…
Last modified: Jul 11, 2026
Vertex Deletion — G minus vertex B
G minus vertex B: vertex B is removed (shown faded in red) along with ALL edges incident to it — AB…
Last modified: Jul 11, 2026
Edge Deletion — G minus edge BE
G minus edge BE: the edge BE is removed (shown in red, faded) but both endpoints B and E remain as …
Last modified: Jul 11, 2026
Induced Subgraph of K4 — G[{Alice,Bob,Charlie}]
The induced subgraph G[{Alice,Bob,Charlie}]: ALL edges between the chosen vertices are automaticall…
Last modified: Jul 11, 2026
Regular Subgraph of K4 — Cherry-Picked Edges
A regular (non-induced) subgraph of K4: vertices {Alice, Bob, Charlie} are chosen but only edge Ali…
Last modified: Jul 11, 2026
Social Network K4 — Alice, Bob, Charlie, Diana
A complete graph K4 representing a social network where all 4 people are mutual friends. Every pair…
Last modified: Jul 11, 2026
Invalid Subgraph Attempt — Missing Endpoint
An invalid subgraph attempt: edge BE is included but vertex B is not in the vertex set. This violat…
Last modified: Jul 11, 2026
Valid Subgraph H of G
A valid subgraph H of G using vertices {A, B, D, E} and edges {AB, AD, DE}. The subgraph edges are …
Last modified: Jul 11, 2026
Subgraph Example — Parent Graph G
The full parent graph G: 6 vertices A-F and 8 edges. This is the source graph from which all subgra…
Last modified: Jul 11, 2026
Walk Base Graph — Neighbourhood
The base graph used in the Walks in Graphs post. Vertices A–E form a small neighbourhood: A-B acros…
Last modified: Jul 11, 2026
Walk Example: A → B → D → E (Open Walk)
Open walk of length 3 on the neighbourhood graph. The traversed edges A-B, B-D, D-E are highlighted…
Last modified: Jul 11, 2026
Walk Example: C → D → C → A (Repeated Edge)
Walk of length 3 where edge C-D is traversed twice (once forward, once back). Orange highlights sho…
Last modified: Jul 11, 2026
Walk Example: A → B → D → C → A (Closed Walk)
Closed walk of length 4 tracing the square A-B-D-C-A. All four edges of the square are highlighted …
Last modified: Jul 11, 2026
Cycle Example — C₅ (Closed, No Repeated Vertices)
A 5-cycle C5: A→B→C→D→E→A. Every vertex except the start/end is visited exactly once. Every edge is…
Last modified: Jul 11, 2026
Circuit Example (Closed, No Repeated Edges)
A circuit A→B→C→D→A on a graph that also has extra edges. All four edges of the square are traverse…
Last modified: Jul 11, 2026
Path Example (No Repeated Vertices or Edges)
A path A→B→C→D→E on a 5-vertex graph. Every vertex and every edge is visited exactly once. All trav…
Last modified: Jul 11, 2026
Trail Example (No Repeated Edges)
A trail on a 5-vertex graph: A→B→C→D→B→E. Vertex B is visited twice but no edge is used more than o…
Last modified: Jul 11, 2026
Strongly Connected Directed Graph
A strongly connected directed graph: from every vertex you can reach every other vertex by followin…
Last modified: Jul 11, 2026
2-Connected Graph (No Cut Vertex)
A 2-connected (biconnected) graph: every vertex has at least 2 vertex-disjoint paths to every other…
Last modified: Jul 11, 2026
Bridge Edge Example
Edge B-C (red) is a bridge — the only connection between the left cluster {A,B} and the right clust…
Last modified: Jul 11, 2026
Cut Vertex (Articulation Point) Example
Vertex B (red) is a cut vertex — removing it splits the graph into two disconnected parts: {A,C} on…
Last modified: Jul 11, 2026
Connected Graph — Single Component
A connected graph: every vertex can reach every other vertex via some path. There is exactly one co…
Last modified: Jul 11, 2026
Disconnected Graph — Three Components
A disconnected graph with three connected components: Component 1 = triangle {A,B,C} (orange), Comp…
Last modified: Jul 11, 2026
Hierholzer's Algorithm — Step-by-Step Graph
A graph for demonstrating Hierholzer's algorithm for finding Eulerian circuits. Two cycles share ve…
Last modified: Jul 11, 2026
Eulerian Trail — Exactly Two Odd-Degree Vertices
A graph with exactly two odd-degree vertices: A (deg 3, orange) and E (deg 3, orange). All other ve…
Last modified: Jul 11, 2026
Eulerian Circuit Example — All Even Degrees
A graph where every vertex has even degree: A(deg 4), B(deg 2), C(deg 4), D(deg 2), E(deg 2), F(deg…
Last modified: Jul 11, 2026
Square with Diagonals — Not Eulerian (Odd Degrees)
A square A-B-C-D with both diagonals A-C and B-D added. Every vertex has degree 3 (odd). By Euler's…
Last modified: Jul 11, 2026
House Shape — Eulerian Graph (All Even Degrees)
A 'house' graph: a square base (A,B,C,D) with a triangular roof (D,E,A). Degrees: A=3+1=4 (even), B…
Last modified: Jul 11, 2026
Seven Bridges of Königsberg
The historic Königsberg bridge graph. Four landmasses (vertices): North bank (N, deg 3), South bank…
Last modified: Jul 11, 2026
Map Coloring - Four Color Theorem
Six regions: a central hub region bordered by five outer ring regions. Each outer region also borde…
Last modified: Jul 11, 2026
Exam Scheduling — Graph Coloring Application
5 exams (Math, CS, Physics, History, English). Edges connect exams that share at least one student …
Last modified: Jul 11, 2026
Greedy Coloring Demonstration
A 5-vertex graph showing greedy coloring in vertex order A,B,C,D,E. A gets red (first color). B is …
Last modified: Jul 11, 2026
Complete Graph K₄ — χ = 4
K₄: every vertex adjacent to every other. Each of the 4 vertices must get a unique color. No two ve…
Last modified: Jul 11, 2026
Wheel Graph W₆ — χ = 4 (Odd Outer Cycle)
Wheel graph W₆: hub H connected to all 5 outer vertices forming a C₅. The C₅ outer ring needs 3 col…
Last modified: Jul 11, 2026
Wheel Graph W₅ — χ = 3 (Even Outer Cycle)
Wheel graph W₅: hub H connected to all 4 outer vertices forming a C₄. The hub H gets its own color …
Last modified: Jul 11, 2026
Odd Cycle C₅ — 3-Chromatic (χ = 3)
The 5-cycle C₅. Alternating red-blue around the ring puts vertex 5 as red — but vertex 5 is adjacen…
Last modified: Jul 11, 2026
Even Cycle C₄ — 2-Colorable (χ = 2)
The 4-cycle C₄ (square) with alternating red-blue coloring. Even cycles are bipartite, so χ = 2. Th…
Last modified: Jul 11, 2026
Triangle K₃ — 3-Chromatic (χ = 3)
A triangle K₃: every vertex is adjacent to every other. Each vertex gets a unique color — red, blue…
Last modified: Jul 11, 2026
2-Colorable Graph — Bipartite Proper Coloring
A bipartite graph with a proper 2-coloring: Set A vertices are red, Set B vertices are blue. No two…
Last modified: Jul 11, 2026
1-Colorable Graph — All Isolated Vertices
A graph with 5 isolated vertices and no edges. Since no two vertices are adjacent, every vertex can…
Last modified: Jul 11, 2026
Spanning Tree 2 — Delete Edge EA
A different spanning tree of the same 5-vertex graph, obtained by deleting edge E-A instead. Result…
Last modified: Jul 11, 2026
Spanning Tree 1 — Delete Edge BD
A spanning tree of the 5-vertex cycle+chord graph, obtained by deleting edge BD. Result: 5 vertices…
Last modified: Jul 11, 2026
Spanning Tree Source — Graph with Cycles
A connected graph with 5 vertices and 6 edges — more than the 4 edges a spanning tree needs. Contai…
Last modified: Jul 11, 2026
Tree 2-Coloring by Even/Odd Depth
The same rooted tree colored by depth parity. Even-depth vertices (d=0,2) are orange: R, D, E, F. O…
Last modified: Jul 11, 2026
Rooted Tree — Parent, Child, Leaf, Depth Labels
A rooted tree with root R at depth 0. B and C are children of R (depth 1, each has R as parent). D,…
Last modified: Jul 11, 2026
Tree — Unique Path Between Any Two Vertices
A tree with 7 vertices. Orange edges highlight the ONLY path from P to Q: P-B-A-C-Q. No other route…
Last modified: Jul 11, 2026
Not a Tree — Disconnected (Forest of Two Trees)
6 vertices, 4 edges. Acyclic — no cycles anywhere. But NOT a tree because it is disconnected: compo…
Last modified: Jul 11, 2026
Not a Tree — Contains a Cycle
5 vertices, 5 edges. Since |E| = |V| (not |V|-1 = 4), the graph cannot be a tree. The red edges A-B…
Last modified: Jul 11, 2026
Simple Tree — 6 Vertices, 5 Edges
A tree with 6 vertices and 5 edges demonstrating |V| = |E| + 1 (6 = 5 + 1). Connected (one componen…
Last modified: Jul 11, 2026
Forest Example — Three Disjoint Trees
A forest containing three separate tree components. Component 1 (orange): A-B-C path. Component 2 (…
Last modified: Jul 11, 2026
Ramsey K₆ Coloring
K6 with edges colored red (friends) or blue (strangers). Node A has 3 red edges → by Pigeonhole, B-…
Last modified: Jul 08, 2026
Complete Bipartite Graph K₃,₃ (Utility Graph)
K3,3: the famous utility graph. Every vertex in Set A (3 orange) connects to every vertex in Set B …
Last modified: Jul 08, 2026
Complete Bipartite Graph K₂,₃
The complete bipartite graph K2,3: every vertex in Set A (2 orange vertices) is connected to every …
Last modified: Jul 08, 2026
Degree Sum Theorem — Bipartite Example
The exact graph from the Degree Theorem proof: Set A = {X, Y}, Set B = {L, M, N}. X connects to L a…
Last modified: Jul 08, 2026
Dogs and Owners — Bipartite
A real-world bipartite graph: dogs (orange) on the left, owners (teal) on the right. Edges represen…
Last modified: Jul 08, 2026
C₆ — Even Cycle (Is Bipartite)
The 6-cycle C6 is bipartite. Odd-positioned vertices (1,3,5) form Set A (orange) and even-positione…
Last modified: Jul 08, 2026
C₅ — Odd Cycle (Not Bipartite)
The 5-cycle C5. Odd cycles cannot be 2-colored without conflict. Starting from vertex 1 (orange), a…
Last modified: Jul 08, 2026
Triangle — Not Bipartite (Odd Cycle)
A triangle (C3) with 3-coloring attempt shown. Any graph containing an odd-length cycle cannot be b…
Last modified: Jul 08, 2026
Bipartite 2-Coloring Demo
A bipartite graph demonstrating the 2-coloring property. Orange vertices form one partition, teal v…
Last modified: Jul 08, 2026
Simple Bipartite Graph
A basic bipartite graph with 3 vertices in Set A (orange) and 3 in Set B (teal). Edges only cross b…
Last modified: Jul 08, 2026
Star Graphs S1-S5
A colored graph containing star graphs S1 through S5
Last modified: Jun 11, 2026
Complete Graph K4 - Maximum Size
K4 showing max edges: n(n-1)/2 = 6.
Last modified: Dec 27, 2025
Graph with Isolated Vertex
F is isolated (degree 0). Other vertices have degrees 1–3.
Last modified: Dec 27, 2025
Degree Sequence Example
Degree sequence (3,3,2,1,1,0). Sum=10=2x5 edges.
Last modified: Dec 27, 2025
Non-Graphic Sequence Demo
Sequence (4,3,2,1) is not graphic: v1 needs deg 4 but only 3 other vertices exist.
Last modified: Dec 27, 2025
Regular Graph - All Same Degree
Pentagon C5 — every vertex has degree 2.
Last modified: Dec 27, 2025
Minimum and Maximum Degree
delta(G)=1, Delta(G)=4. Center hub with 4 spokes.
Last modified: Dec 27, 2025
Handshaking Lemma Demonstration
5 edges. Sum of degrees = 2x5 = 10.
Last modified: Dec 27, 2025
Road Network Example
A simple road network connecting four towns: Springfield, Riverside, Hilltop, and Lakeside. Demonst…
Last modified: Dec 27, 2025
Havel-Hakimi Example Graph
Degree sequence [3,3,2,2,2]. A and B have degree 3; C, D, E have degree 2.
Last modified: Dec 27, 2025
Small Graph - Order 4
Path graph P4: 4 vertices, 3 edges. Demonstrates order and size.
Last modified: Dec 27, 2025
Pigeonhole Coloring Example
12 vertices colored with only 10 colors. Nodes 1 and 12 are both red; nodes 2 and 11 are both blue.…
Last modified: Dec 27, 2025
3-Regular Graph (Order 6)
Hexagon with 3 diagonals. Every vertex has degree 3. 9 edges.
Last modified: Dec 27, 2025
1-Regular Graph (Order 4)
Two disconnected edges (perfect matching). Each vertex has degree 1.
Last modified: Dec 27, 2025
2-Regular Graph (Order 5)
Pentagon cycle C5 — each vertex has degree 2.
Last modified: Dec 27, 2025
Complete Graph K4 (3-Regular)
K4 — 4 vertices each connected to all 3 others. 6 edges.
Last modified: Dec 27, 2025
Solution: 1-Regular of Order 2
A single edge — smallest 1-regular graph.
Last modified: Dec 27, 2025
Solution: 1-Regular of Order 6
Three disjoint edges — perfect matching on 6 vertices.
Last modified: Dec 27, 2025
Solution: 2-Regular of Order 3 (Triangle)
Triangle C3 — smallest 2-regular graph.
Last modified: Dec 27, 2025
Solution: K5 Complete Graph (4-Regular)
K5 — 5 vertices, 10 edges, 4-regular.
Last modified: Dec 27, 2025
Solution: 4-Regular of Order 6
Hexagon + diagonals + second-neighbour edges. Every vertex has degree 4. 12 edges.
Last modified: Dec 27, 2025
Solution: K6 Complete Graph (5-Regular)
K6 — 6 vertices, 15 edges, 5-regular.
Last modified: Dec 27, 2025
Cube Graph (3-Regular)
Cube graph Q3 — 3-regular, 8 vertices, 12 edges.
Last modified: Dec 27, 2025
Octahedron Graph (4-Regular)
Octahedron graph — 4-regular, 6 vertices, 12 edges.
Last modified: Dec 27, 2025
Cycle C4 (Square)
Square — 2-regular graph of order 4.
Last modified: Dec 27, 2025
Icosahedron Graph (5-Regular)
Icosahedron — 5-regular, 12 vertices, 30 edges.
Last modified: Dec 27, 2025
Simple Tree
A tree structure with no cycles, showing a hierarchical relationship.
Last modified: Nov 04, 2025
Flight Map
A map connecting a few major cities
Last modified: Nov 04, 2025
Bipartite Job Applicants
A bipartite graph showing job applicants and the positions they qualify for.
Last modified: Nov 04, 2025
One-Way Streets
A directed graph showing one-way streets between intersections A, B, and C.
Last modified: Nov 04, 2025
Undirected Friendship Graph
An example showing symmetric friendships in an undirected graph.
Last modified: Nov 04, 2025
Simple Social Network
A basic example of a social network showing friendships between Alice, Bob, Charlie, and Diana.
Last modified: Nov 04, 2025
Graph Representation
Several ways of drawing the same graph
Last modified: Jul 24, 2025
Graph Examples
Graphs are networks of points and lines
Last modified: Jul 24, 2025
Petersen Graph
The Petersen graph, a well-known counterexample in graph theory
Last modified: Jul 22, 2025
Cycle Graphs C1-C6
A graph containing cycle graphs C1 through C6 as disconnected components
Last modified: Jul 22, 2025
Complete Graph K4
A complete graph with 4 vertices and 6 edges (K4)
Last modified: Jul 22, 2025
Complete Graph K5
A complete graph with 5 vertices and 10 edges (K5)
Last modified: Jul 22, 2025
Complete Graphs K1, K2, K3
A graph containing K1, K2, and K3 as disconnected components
Last modified: Jul 22, 2025