1.

Multigraphs, Weighted Graphs, Directed Graphs

So far, we've mostly discussed simple graphs. Let's explore some important variations. 🗺️
Multigraphs A multigraph is a graph that is permitted to have multiple edges (also called
parallel edges) between the same pair of vertices. It still does not allow loops.

●​ Examples:
1.​ Flight Routes: Imagine two cities, Delhi and Mumbai. There might be several
different flights (e.g., morning, evening, night) operating between them. A
multigraph can represent this by having three parallel edges between the
"Delhi" vertex and the "Mumbai" vertex.
2.​ Network Connections: In a computer network, there might be multiple
physical ethernet cables connecting two crucial routers for redundancy and
increased bandwidth.
3.​ The Seven Bridges of Königsberg: The original problem is a classic
example of a multigraph, where multiple bridges (edges) connected the same
landmasses (vertices).

Weighted Graphs A weighted graph is a graph where each edge is assigned a numerical
weight or cost. This weight can represent distance, time, capacity, or any other measurable
quantity.

●​ Examples:
1.​ Road Networks: A graph of cities can have edges weighted by the distance
in kilometers between them. This is used by GPS services to find the shortest
route.
2.​ Computer Networks: The weight of an edge between two routers could
represent the latency (delay) of the connection in milliseconds. Network
routing protocols use this to find the fastest path for data.
3.​ Cost of Flights: The edges between airport cities can be weighted by the
ticket price for that flight.
4.​ Social Networks: The weight of an edge between two people could
represent the "strength" of their connection, perhaps measured by the
number of messages they exchange.

Directed Graphs (Digraphs) A directed graph or digraph is a graph where the edges
have a direction. An edge is an ordered pair of vertices (u, v), represented by an arrow from
u to v. u is the tail and v is the head.

●​ Examples:
1.​ Street Maps: In a city with one-way streets, the road network must be
modeled as a digraph. An edge (A, B) means you can drive from intersection
A to B, but not necessarily from B to A.
2.​ Social Media "Follows": On platforms like Twitter or Instagram, the "follow"
relationship is directed. If A follows B, it doesn't mean B must follow A.
2. Adjacency & Incidence Matrix Representations

Matrices provide an algebraic way to represent graphs, which is ideal for computer
processing.

Adjacency Matrix For a graph G with n vertices {v1, v2, ..., vn}, the adjacency matrix A is
an n x n matrix where:

●​ A[i, j] = 1 if there is an edge between vi and vj.

●​ A[i, j] = 0 if there is no edge between vi and vj.

For a digraph, A[i, j] = 1 if there is an edge from vi to vj. For a weighted graph, the entry is
the weight of the edge instead of 1. For a multigraph, the entry can be the number of edges
between the vertices.

Incidence Matrix For a graph G with n vertices {v1, ..., vn} and m edges {e1, ..., em}, the
incidence matrix M is an n x m matrix where:

●​ M[i, j] = 1 if vertex vi is an endpoint of edge ej.

●​ M[i, j] = 0 otherwise.

Example 1: Undirected Graph V = {1, 2, 3, 4}, E = {e1={1,2}, e2={1,3}, e3={2,3}, e4={3,4}}

●​

Example 2: Directed Graph V = {A, B, C}, E = {(A,B), (B,C), (C,A), (B,A)}

●​

3. Isomorphism

Concept Two graphs are isomorphic if they are structurally identical, even if they are drawn
differently or have different vertex labels. They represent the same network structure.

Formally, two graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there exists a
bijection (a one-to-one and onto function) f: V1 -> V2 such that any two vertices u and v are
adjacent in G1 if and only if f(u) and f(v) are adjacent in G2. This function f is called an
isomorphism.
Classic Example: The Petersen Graph The Petersen graph is famous for having many
different-looking but isomorphic drawings. The standard pentagon-with-a-star-inside drawing
and the drawing with a central hub are both the same graph.

Non-Classic Example Are these two graphs isomorphic?

●​ G1: A cycle of 6 vertices (C6).

●​ G2: Two disjoint triangles (K3 and K3). No. Although they both have 6 vertices and 6
edges, they are structurally different. G1 is connected, while G2 is not. An
isomorphism must preserve such properties.

Challenges The Graph Isomorphism Problem—determining whether two graphs are

isomorphic—is a famous unsolved problem in computational complexity theory. While no
efficient (polynomial-time) algorithm is known for all graphs, it is not known to be
NP-complete either. For most practical cases, computers can determine isomorphism
relatively quickly, but a general, fast solution remains elusive.
4. Non-Isomorphic Graphs

To prove two graphs are not isomorphic, we need to find a structural property (a graph
invariant) that is different between them.

Graph Invariants to Check:

1.​ Number of vertices (|V|)

2.​ Number of edges (|E|)
3.​ Degree sequence
4.​ Connectivity (Is one connected and the other not?)
5.​ Presence and length of cycles (Does one have a 3-cycle (triangle) while the other
doesn't?)
6.​ Number of connected components.

Full Example: Prove that the following two graphs, G and H, are not isomorphic.

●​ Graph G: A 5-cycle with a chord (C5 with edge {1,3}). V={1,2,3,4,5},

E={{1,2},{2,3},{3,4},{4,5},{5,1},{1,3}}
●​ Graph H: A 5-cycle with a "tail". V={a,b,c,d,e,f}, E={{a,b},{b,c},{c,d},{d,e},{e,a},{c,f}}

Analysis:

1.​ Vertices: |V_G| = 5, |V_H| = 6. The number of vertices is different.

○​ Conclusion: The graphs are not isomorphic. This is the easiest check.

Let's try a harder example where invariants match. G: A C6 (a hexagon). H: Two disjoint K3s
(two separate triangles).
 1.​ Vertices: |V_G| = 6, |V_H| = 6. (Match)
2.​ Edges: |E_G| = 6, |E_H| = 3+3=6. (Match)
3.​ Degree Sequence:
○​ G: Every vertex has degree 2. Sequence is {2,2,2,2,2,2}.
○​ H: Every vertex has degree 2. Sequence is {2,2,2,2,2,2}. (Match)
4.​ Connectivity:
○​ G is connected.
○​ H is disconnected (it has two components).
○​ Since connectivity is a structural property that must be preserved by an
isomorphism, and the graphs differ in this property, they cannot be
isomorphic.
○​ Conclusion: The graphs are not isomorphic.

5. Complement of a Graph

The complement of a simple graph G, denoted G_bar, is a graph with the same vertex set
V as G, but whose edge set contains exactly the edges that are not in G.

Two vertices are adjacent in G_bar if and only if they are not adjacent in G.

Example: Let G be a path graph P4.

●​ V = {1, 2, 3, 4}
●​ E = { {1,2}, {2,3}, {3,4} }

To find the complement G_bar:

●​ Start with the same vertices {1,2,3,4}.

●​ The complete graph on 4 vertices (K4) has edges {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}.
●​ The edges in G_bar are the edges from K4 minus the edges from G.
●​ E_bar = { {1,3}, {1,4}, {2,4} }.
6. Self Complementary Graphs

A graph G is self-complementary if it is isomorphic to its own complement (G ≈ G_bar).

Properties:

●​ If a self-complementary graph has n vertices, it must have exactly half the edges of a
complete graph Kn. So, |E| = (n(n-1)/2) / 2 = n(n-1)/4.
●​ This implies that n(n-1) must be divisible by 4, which means n must be of the form 4k
or 4k+1. A graph on 6 vertices cannot be self-complementary.
●​ Example: The path graph P4 is self-complementary. The cycle graph C5 is also
self-complementary.

Connectedness & Disconnectedness Theorem: If a graph G is disconnected, its

complement G_bar must be connected.

Proof Sketch:

1.​ Let G be a disconnected graph. This means its vertices can be partitioned into at
least two components, say C1 and C2.
2.​ Take any vertex u from component C1 and any vertex v from component C2.
3.​ In the original graph G, there is no edge between u and v (otherwise they would be in
the same component).
4.​ By the definition of a complement, since the edge {u,v} is not in G, it must be in
G_bar.
5.​ This means that in G_bar, every vertex in C1 is connected to every vertex in C2.
6.​ This ensures that there is a path between any two vertices in G_bar (you can go from

✅
any vertex to a vertex in another component, and then to any other vertex).
7.​ Therefore, G_bar is connected.

7. Bipartite Graphs

A graph G is bipartite if its vertex set V can be partitioned into two disjoint subsets, V1 and
V2, such that every edge in G connects a vertex in V1 to a vertex in V2. No edge connects
two vertices within the same subset.

V = V1 U V2 and V1 ∩ V2 = ∅.

Litmus Test: A graph is bipartite if and only if it has no odd-length cycles.

Examples:

●​ All trees are bipartite.

●​ All even cycles (C4, C6, etc.) are bipartite.
●​ The cube graph is bipartite.
●​ A triangle (C3) is not bipartite because it has a cycle of length 3 (an odd number).
8. A puzzle involving Bipartite Graphs

Theorem: A graph is bipartite if and only if it is 2-colorable.

Proof:

Part 1: If a graph is bipartite, then it is 2-colorable.

1.​ Assume G is bipartite. This means its vertex set V can be partitioned into V1 and V2.
2.​ Create a coloring C. For every vertex v in V1, assign it Color 1. For every vertex v in
V2, assign it Color 2.
3.​ Consider any edge {u,v} in G. By the definition of a bipartite graph, u and v must be
in different partitions.

✅
4.​ Therefore, u and v will have different colors (one has Color 1, the other has Color 2).
5.​ This is a proper 2-coloring of the graph.

Part 2: If a graph is 2-colorable, then it is bipartite. (The Converse)

1.​ Assume G is 2-colorable with colors, say, Red and Blue.

2.​ Create two sets. Let V1 be the set of all vertices colored Red. Let V2 be the set of all
vertices colored Blue.
3.​ These two sets are disjoint (V1 ∩ V2 = ∅) and together they cover all vertices (V1 U
V2 = V). So they form a partition.
4.​ Consider any edge {u,v} in G. By the definition of a proper coloring, adjacent vertices
must have different colors.
5.​ This means that one of {u,v} is in V1 (Red) and the other is in V2 (Blue).

✅
6.​ Therefore, no edge connects two vertices within the same set.
7.​ This is the definition of a bipartite graph.

9. Eulerian Graphs

An Eulerian circuit (or Euler tour) is a trail in a graph that visits every edge exactly once
and starts and ends at the same vertex. A graph that contains an Eulerian circuit is called an
Eulerian graph.

An Eulerian trail (or Euler path) visits every edge exactly once but starts and ends at
different vertices.

Illustration: The Königsberg Bridge Problem The problem was to find an Eulerian
trail/circuit in the graph of the city. Euler proved it was impossible.
Litmus Test:

●​ A connected graph has an Eulerian circuit if and only if every vertex has an even
degree.
●​ A connected graph has an Eulerian trail if and only if it has exactly two vertices of
odd degree. The trail must start at one of the odd-degree vertices and end at the
other.

Example 1: Is the graph of a pentagon with a star inside (K5) Eulerian?

●​ It is a complete graph on 5 vertices.

●​ Every vertex has degree n-1 = 4.
●​ All degrees are even. Yes, it has an Eulerian circuit.

Example 2: The Königsberg Graph

●​ The degrees of the four landmasses (vertices) were {5, 3, 3, 3}.

●​ There are four vertices of odd degree.
●​ Since it's not 0 or 2, it has neither an Eulerian circuit nor an Eulerian trail.
10. Proof of Even degree implies Eulerian Graph

Theorem: A connected multigraph G has an Eulerian circuit if and only if every vertex has
an even degree.

Proof Sketch ("If" part - Fleury's Algorithm intuition):

1.​ Start anywhere. Since all degrees are even, you can always leave a vertex that you
enter. The only exception is the starting vertex.
2.​ Construct a trail. Start at a vertex v and follow a trail, never using the same edge
twice. Since every vertex has an even degree, whenever you enter an intermediate
vertex u, there must be an unused edge to leave u. You will never get "stuck" at an
intermediate vertex.
3.​ Return to start. Since the graph is finite, you must eventually return to the starting
vertex v. This creates a closed trail C.
4.​ Check for unused edges. If this trail C used all edges of the graph, we are done.
5.​ If not, find a connection. If there are unused edges, since the graph is connected,
there must be a vertex u on our trail C that is connected to the part of the graph with
unused edges.
6.​ Splice in a new tour. Starting from u, create a new tour C' using only the unused
edges. This is possible for the same reason as before (all vertices in the remaining
graph still have even degrees).
7.​ Combine. Traverse the original circuit C until you get to u, then traverse the new tour
C', and then finish traversing C. This creates a larger closed trail.

✅
8.​ Repeat. Repeat this process until all edges are used. The final result is an Eulerian
circuit.

11. Hamiltonian Graphs

A Hamiltonian path is a path in a graph that visits every vertex exactly once. A
Hamiltonian cycle (or circuit) is a Hamiltonian path that is a cycle (it starts and ends at the
same vertex). A graph that contains a Hamiltonian cycle is called a Hamiltonian graph.

Illustration: The "traveling salesman problem" is about finding the shortest Hamiltonian
cycle in a weighted complete graph.

Non-Examples:

●​ A graph with a cut vertex cannot have a Hamiltonian cycle.

●​ A tree (with more than 2 vertices) cannot have a Hamiltonian cycle because it has no
cycles at all.

Important Results: Unlike Eulerian graphs, there is no simple, necessary and sufficient
condition (like the degree test) to know if a graph is Hamiltonian. Determining if a graph has
a Hamiltonian cycle is a classic NP-complete problem, meaning it's computationally very
hard for large graphs.
12. Results about connectedness and paths

●​ Theorem: If there is a walk between two distinct vertices u and v in a graph G, then
there must also be a path between u and v. This result is important because it means
that to check if two vertices are connected, we only need to see if a path exists
between them.
●​ Testing for Connectivity: Algorithms like Breadth-First Search (BFS) or Depth-First
Search (DFS) can be used to test for connectivity. Start a search from an arbitrary
vertex s, find all vertices that are reachable from s, if the set of reachable vertices is
equal to the set of all vertices V, the graph is connected.

13. Dirac's Theorem (1952)

This provides a sufficient (but not necessary) condition for a graph to be Hamiltonian.

Theorem: If G is a simple graph with n vertices (n >= 3), and the degree of every vertex is at
least n/2, then G is Hamiltonian. deg(v) >= n/2 for all v ∈ V.

Proof Sketch: The proof is by contradiction. Assume a graph G satisfies Dirac's condition
but does not have a Hamiltonian cycle. Let P be a path of the longest possible length in G,
with endpoints v1 and vk. Since P is maximal, all neighbors of v1 and vk must lie on the path
P. Then, using a clever pigeonhole-like argument on the neighbors of v1 and vk along the
path, one can show that there must exist a cycle of length k. Further arguments show that
this cycle must, in fact, include all n vertices, which contradicts the initial assumption.

14. Ore's Theorem (1960)

This is a generalization of Dirac's theorem. It's a stronger condition (it applies to more
graphs).

Theorem: If G is a simple graph with n vertices (n >= 3), and for every pair of non-adjacent
vertices u and v, the sum of their degrees is at least n, then G is Hamiltonian. deg(u) +
deg(v) >= n for all non-adjacent u, v.

Proof Sketch: Similar to Dirac's theorem, the proof is by contradiction. Assume a graph
satisfies Ore's condition but is not Hamiltonian. Consider a maximal path. Show that the
endpoints of this path must be adjacent to form a cycle. Then, show that this cycle must
contain all vertices of the graph, leading to a contradiction.
15. Dirac vs Ore

●​ Ore's Theorem implies Dirac's Theorem.

●​ Proof: If a graph G satisfies Dirac's condition, then deg(v) >= n/2 for all v. Now
consider any pair of non-adjacent vertices u and v.
○​ deg(u) >= n/2
○​ deg(v) >= n/2
○​ Therefore, deg(u) + deg(v) >= n/2 + n/2 = n.
○​ This satisfies Ore's condition.
●​ So, any graph that is Hamiltonian by Dirac's theorem is also Hamiltonian by Ore's
theorem. However, there are graphs that satisfy Ore's condition but not Dirac's (e.g.,
a graph on 4 vertices with degree sequence {3,3,2,2}).

16. Eulerian and Hamiltonian Relationship

There is no direct relationship between a graph being Eulerian and being Hamiltonian. The
two concepts measure entirely different properties.

●​ Eulerian: About visiting edges.

●​ Hamiltonian: About visiting vertices.

A graph can be:

1.​ Both Eulerian and Hamiltonian: e.g., a cycle Cn for n >= 3.

2.​ Eulerian but not Hamiltonian: e.g., the "figure-eight" graph formed by two K3s
sharing a single vertex. Every vertex has an even degree, but the cut vertex prevents
a Hamiltonian cycle.
3.​ Hamiltonian but not Eulerian: e.g., a cube graph where a path visits every vertex
once, but not every edge. A cube is 3-regular, so it has odd-degree vertices.
4.​ Neither: e.g., the Petersen graph (not Hamiltonian) with its odd degrees (not
Eulerian).

17. Applications of Eulerian and Hamiltonian Graphs in CS

●​ Eulerian Circuits:
○​ Route Inspection Problem (Chinese Postman Problem): Finding the
shortest route that traverses every street in a neighborhood (e.g., for mail
delivery or garbage collection). If the graph is Eulerian, the route is simply the
circuit. If not, edges must be re-traversed, and the goal is to minimize this.
○​ Genome Sequencing: In bioinformatics, assembling DNA fragments can be
modeled as finding an Eulerian path in a de Bruijn graph.
 ●​ Hamiltonian Cycles:
○​ Traveling Salesman Problem (TSP): A classic optimization problem to find
the shortest possible route that visits a set of cities and returns to the origin.
This is equivalent to finding the minimum weight Hamiltonian cycle in a
complete weighted graph. It has applications in logistics, planning, and
manufacturing.
○​ Circuit Board Drilling: To minimize the time a drill takes to make holes in a
circuit board, the path it follows should be a short Hamiltonian path.

18. Planar Graphs

Puzzle: The Three Utilities Problem. Can you connect 3 houses to 3 utilities (Gas, Water,
Electric) without any lines crossing?

●​ This is a question about the graph K3,3 (a complete bipartite graph).

●​ The answer is no, it's impossible to draw K3,3 on a plane without edges crossing.

A planar graph is a graph that can be drawn in a plane such that no two edges cross each
other. Such a drawing is called a planar embedding.

Examples:

1.​ Any tree is planar.

2.​ Any cycle (Cn) is planar.
3.​ The complete graph K4 is planar.

Non-Examples:

1.​ The complete graph K5 is not planar.

2.​ The complete bipartite graph K3,3 (the utilities graph) is not planar.
19. Euler's Formula: V - E + R = 2

For any connected planar graph, Euler's formula relates the number of vertices (V), edges
(E), and regions (R or F for faces) in a planar embedding. The regions include the outer,
unbounded region.

Theorem: V - E + R = 2

Illustration: Consider a drawing of K4.

●​ V=4
●​ E=6
●​ R = 4 (three "inner" triangular regions and one "outer" region).
●​ Check the formula: 4 - 6 + 4 = 2. It holds.

Proof Sketch (by Induction on the number of edges):

1.​ Base Case: If E = 0, then V = 1. The graph is a single dot. R=1 (the outer region). 1 -
0 + 1 = 2. The formula holds.
2.​ Inductive Hypothesis: Assume the formula holds for any connected planar graph
with k edges.
3.​ Inductive Step: Consider a graph G with k+1 edges.
○​ Case 1: G is a tree. A tree has no cycles. R=1. A tree with n vertices has n-1
edges. So V - E + R = n - (n-1) + 1 = 2.
○​ Case 2: G has a cycle. Find an edge e that is part of a cycle. Removing e will
merge the two regions on either side of it into one, decreasing R by 1. The
new graph G' has V vertices, E-1 edges, and R-1 regions. G' is still
connected. By the inductive hypothesis, the formula holds for G': V - (E-1) +

✅
(R-1) = 2. Simplifying gives V - E + R = 2.
4.​ The formula holds for G. By induction, it is true for all connected planar graphs.
20. Litmus Test for Planarity

Kuratowski's Theorem: A graph is planar if and only if it does not contain a subgraph that
is a subdivision of K5 or K3,3. A subdivision is created by adding vertices of degree 2 along
edges.

This theorem is powerful but hard to use directly. A simpler, necessary (but not sufficient)
test comes from Euler's formula.

Corollary of Euler's Formula: For any simple, connected planar graph with V >= 3:

1.​ E <= 3V - 6
2.​ If the graph has no triangles (C3), then E <= 2V - 4.

Litmus Test:

1.​ Given a graph, check if E <= 3V - 6. If this inequality is false, the graph is definitely
not planar.
2.​ If the inequality is true, the graph might be planar (this test is not conclusive).

Worked Example (K5):

●​ V = 5, E = 10.
●​ Check E <= 3V - 6: Is 10 <= 3(5) - 6?
●​ Is 10 <= 15 - 6? Is 10 <= 9? False.
●​ Conclusion: K5 is not planar.

Worked Example (K3,3):

●​ V = 6, E = 9.
●​ Check E <= 3V - 6: Is 9 <= 3(6) - 6? Is 9 <= 12? True. This test is inconclusive.
●​ But K3,3 has no triangles. So we must use the stronger condition: E <= 2V - 4.
●​ Is 9 <= 2(6) - 4? Is 9 <= 12 - 4? Is 9 <= 8? False.
●​ Conclusion: K3,3 is not planar.

21. Coloring of Graphs

Prisoners & Cells Puzzle: A warden wants to assign prisoners to different cell blocks. To
prevent collusion, any two prisoners who are enemies must be in different cell blocks. What
is the minimum number of cell blocks needed?

●​ This is a graph coloring problem.

●​ Vertices: The prisoners.
●​ Edges: An edge connects two prisoners if they are enemies.
●​ Colors: The cell blocks.
●​ The goal is to find the chromatic number of the "enemy" graph.
Proper Coloring A proper coloring of a graph is an assignment of a "color" (usually
represented by an integer) to each vertex such that no two adjacent vertices have the same
color.

The chromatic number, χ(G), is the minimum number of colors needed for a proper
coloring of G.

22. Examples of Proper Coloring

1.​ A Tree: Any tree is 2-colorable. χ(Tree) = 2. (Unless it's just one vertex).
2.​ An Even Cycle (C6): Can be colored with 2 colors (e.g.,
Red-Blue-Red-Blue-Red-Blue). χ(C6) = 2.
3.​ An Odd Cycle (C5): Needs 3 colors (e.g., R-B-G-R-B doesn't work). χ(C5) = 3.
4.​ A Complete Graph (K_n): Every vertex is adjacent to every other vertex, so every
vertex needs a unique color. χ(K_n) = n.

23. India Map Coloring Puzzle

Problem: What is the minimum number of colors needed to color a political map of India
such that no two neighboring states have the same color?

Solution: This is an application of the famous Four Color Theorem.

Four Color Theorem: Any planar graph can be colored with at most four colors. χ(G) <= 4
for any planar G.

1.​ A map can be converted into a planar graph: each state is a vertex, and an edge
connects two vertices if the states share a border.
2.​ Since the map of India can be represented as a planar graph, the Four Color
Theorem guarantees that a maximum of 4 colors are needed.
3.​ To show that we need at least 4, we would have to find a subgraph that requires 4
colors (e.g., a K4 as a minor). Looking at the map, states like Rajasthan, Madhya
 Pradesh, Gujarat, and Maharashtra form a cluster where each touches the others (or
is close enough in the graph representation), suggesting that 4 colors are likely
necessary.
4.​ Conclusion: The chromatic number for the map of India is 4.

24. Summary and Conclusion

This chapter delved into advanced concepts and variations within graph theory.

●​ We expanded our vocabulary beyond simple graphs to include multigraphs,

weighted graphs, and directed graphs, each suited for modeling different
real-world scenarios. We represented them using adjacency and incidence
matrices.
●​ The concept of isomorphism was introduced to define structural equivalence, a
computationally challenging but fundamental idea.
●​ We explored special types of graphs, such as bipartite graphs (those with no odd
cycles) and their deep connection to 2-coloring.
●​ Eulerian graphs (traversing every edge once) and Hamiltonian graphs (visiting
every vertex once) were analyzed. While Eulerian graphs have a simple
degree-based test, Hamiltonian graphs are notoriously hard to identify, leading to
famous problems like the Traveling Salesman Problem.
●​ Planar graphs (drawable without edge crossings) were shown to have beautiful
properties governed by Euler's Formula (V-E+R=2). This formula provides a
powerful test to prove that certain graphs, like K5 and K3,3, are non-planar.
●​ Finally, graph coloring was introduced as a way to assign properties (colors) to
vertices with constraints, a problem with wide applications, epitomized by the famous
Four Color Theorem for maps.

Graph theory is a rich and diverse field that provides the mathematical foundation for
understanding networks of all kinds. From optimizing routes and scheduling tasks to
understanding the structure of the internet and social networks, its applications are vast and
continue to grow.