CS 121 › Lesson 7 of 12

Graph Theory

Lesson 7 · OKSTEM College · AS Computer Science

Graphs: Vertices & Edges

A graph G = (V, E) is a set of vertices (nodes) V connected by edges E. Graphs model networks, relationships, maps, schedules, and more.

TermDefinition
Degree of vNumber of edges incident to vertex v
PathSequence of vertices connected by edges, no repeats
CycleA path that starts and ends at the same vertex
Connected graphEvery vertex is reachable from every other
Weighted graphEach edge has a numeric weight (cost, distance)

Handshaking Lemma: In any graph, the sum of all vertex degrees equals 2|E|. Therefore the number of odd-degree vertices is always even.

Directed vs Undirected; Special Graphs

Undirected: edges {u, v} — relationship is symmetric
Directed (digraph): edges (u, v) — one-way relationship

Complete graph Kn: every pair of vertices connected — |E| = n(n−1)/2
Bipartite graph: vertices split into two groups; edges only cross groups
Tree: connected, acyclic, undirected — exactly n−1 edges for n vertices

Euler & Hamiltonian Paths

Euler Path/CircuitHamiltonian Path/Cycle
VisitsEvery edge exactly onceEvery vertex exactly once
ConditionExactly 0 or 2 odd-degree verticesNo known efficient test (NP-complete)
Real-worldRoute delivery trucks, Königsberg bridgesTravelling salesman problem (TSP)

Practice Problems

1. A graph has 5 vertices with degrees 2, 3, 3, 2, 4. How many edges does it have?

Sum of degrees = 2+3+3+2+4 = 14.
Handshaking lemma: |E| = 14/2 = 7 edges.

2. Does Königsberg have an Euler circuit? Why?

No. Königsberg (the original problem) has 4 vertices all with odd degree. An Euler circuit requires every vertex to have even degree. This was proved by Euler in 1736 — the birth of graph theory.

Knowledge Check

The degree of a vertex in an undirected graph is

That's |V|, not a vertex's degree.
Correct — each edge touching the vertex contributes 1 to its degree.
That's eccentricity, not degree.
Unweighted graphs don't have vertex weights; degree is edge count.
Recap: degree(v) = number of edges connected to v. In a directed graph, distinguish in-degree and out-degree.

The Handshaking Lemma states that

Euler path requires 0 or 2 odd-degree vertices.
Correct — ∑deg(v) = 2|E|, since each edge contributes 1 to both its endpoints.
Connected + acyclic = tree; a general connected graph may have cycles.
That would only be true for a vertex connected to every other vertex.
Recap: every edge has two endpoints, so it adds 1 to two degree-sums. Total degree = 2 × edge count.

An Euler circuit exists in an undirected graph if and only if

Degree-2 everywhere works but isn't the necessary condition.
Correct — both conditions are necessary and sufficient.
Trees have many odd-degree vertices and no cycles at all.
Bipartite graphs can have odd-degree vertices; bipartite is unrelated to Euler circuits.
Recap: Euler circuit = traverse every edge exactly once and return to start. Requires: connected + all-even degrees.

A tree with n vertices has

n edges would create a cycle.
Correct — a tree is minimally connected: n vertices, n−1 edges, no cycles.
That's K⊂n; the complete graph.
No standard graph family has 2n edges by definition.
Recap: tree = connected + acyclic. Adding any edge creates a cycle; removing any edge disconnects it. Exactly n−1 edges.

Finding a Hamiltonian cycle is computationally hard because

Storage is not the issue; the algorithm is the issue.
Correct — TSP/Hamiltonian cycle are NP-complete; only exponential algorithms are known.
They exist in many graphs; finding them is just hard.
Handshaking tells us about edge counts, not Hamiltonian cycles.
Recap: Euler path = polynomial time (check degrees). Hamiltonian path = NP-complete (no efficient algorithm known). Same problem on edges vs vertices — wildly different complexity.

← PreviousNext →