Graph Theory: Paths, Trees and Coloring With easy examples.

Graph theory studies networks of points connected by lines. The points are called vertices and the lines are called edges, and together they form a graph. A road map is a graph (cities joined by roads), a social network is a graph (people joined by friendships), and the internet itself is one gigantic graph.

It matters because graphs are the standard model for anything connected. Google Maps finds routes through a road graph, delivery companies optimise trips over graphs, and social platforms recommend friends using graph connections. A huge share of practical computer science is graph algorithms wearing different clothes.

Key Concepts

• Vertex and edge: the basic building blocks. We write G = (V, E) for a graph with vertex set V and edge set E.
• Degree: the number of edges touching a vertex. In a friendship graph, your degree is your friend count.
• Path: a route from one vertex to another with no vertex repeated. Cycle: a path that starts and ends at the same vertex.
• Connected graph: you can reach every vertex from every other vertex by some path.
• Tree: a connected graph with no cycles — like a family tree or a company org chart.
• Bipartite graph: vertices split into two groups with edges only between groups, never inside one, like students connected to the courses they take.
• Graph coloring: assigning colors to vertices so that neighbours always differ; the chromatic number is the fewest colors that work.

Formulas

• Handshaking lemma: the sum of all vertex degrees equals twice the number of edges, because each edge contributes one to the degree of each of its two endpoints. This forces the degree sum to always be even.
• Tree edge count: a tree with n vertices has exactly n − 1 edges. Any connected graph with more edges than that must contain a cycle.
• Complete graph: K_n, where every pair of vertices is joined, has n × (n − 1) / 2 edges. K_5 therefore has 10 edges.
• Complete bipartite graph: K_{m,n} has exactly m × n edges, one for every cross-group pair.

Worked Example

A small office network has 6 routers with degrees 4, 3, 3, 2, 2 and 2. How many cables connect them, and is this degree list even possible?

1. Add the degrees: 4 + 3 + 3 + 2 + 2 + 2 = 16.
2. By the handshaking lemma, edges = 16 / 2 = 8 cables.
3. Check possibility: the degree sum is even, which is required, and no degree exceeds 5 (the maximum neighbours among 6 routers), so the list is plausible.
4. Bonus check: a tree on 6 vertices would have exactly 5 edges, but this network has 8, so it definitely contains cycles — good for backup routes if one cable fails.
5. The average degree is 16 / 6 ≈ 2.67 connections per router, a reasonable density for a small office.

Common Misconceptions

• "Every connected graph is a tree." A tree must also have no cycles. A connected graph with extra edges contains cycles and is not a tree, though every connected graph contains a tree inside it (a spanning tree).
• "Redrawing a graph changes it." Moving vertices around on paper changes nothing about the graph; only which vertices are joined matters. Two drawings of the same connections are the same graph.
• "Coloring a map needs one color per region." Only neighbouring regions must differ, which is why real maps reuse colors. Any planar map needs at most four colors, a famous result called the four color theorem.

Real-World Applications

• Navigation: Google Maps runs shortest-path algorithms on a graph of roads to route you around traffic.
• Social networks: friend suggestions, influencer detection and community finding are all graph computations.
• Scheduling: exam timetables are built by coloring a graph where conflicting exams are joined by edges — same color means the same time slot.
• Dependencies: build tools and package managers order tasks using graphs so that each job runs after the things it needs.

Graphs turn messy connected systems into clean mathematics: count degrees to find edges, spot cycles to judge redundancy, and color to schedule without clashes. Master these few ideas and you can read maps, networks and schedules as the same underlying structure.