Lesson 5-2: Graph Theory Basics

Build intuition for graphs, degrees, connectivity, Euler trails/circuits, bipartite graphs, and Dijkstra's shortest paths.

Learning Objectives

Vertices, Edges, Degree

G=(V,E)

deg(v) = |{ ein E : e ext{ incident to } v }|

Paths and Connectivity

Path: sequence of adjacent vertices; cycle returns to start.

Connected (undirected): every vertex pair has a path.

Strongly connected (directed): paths both directions between any two vertices.

sum_{vin V} deg(v) = 2|E|

Therefore, the number of odd-degree vertices is even.

Euler circuit exists iff the graph is connected (ignoring isolated vertices) and all degrees are even.
Euler trail (but not circuit) exists iff exactly two vertices have odd degree.

V={1,2,3,4}, E={(1,2),(1,3),(2,3),(3,4)}
Degrees: 1→2, 2→2, 3→3, 4→1 → two odd (3,4) → Euler trail exists, no Euler circuit.

A graph is bipartite if vertices split into two sets with edges only across sets. Equivalently, it is 2-colorable. No odd cycles exist.

For non-negative edge weights, Dijkstra expands the node with smallest tentative distance until all distances are finalized.

Edges: 1-2 (3), 1-3 (1), 2-4 (2), 3-4 (4)
Initialization: dist(1)=0; others=∞. Relax neighbors and iterate → dist(4)=5.

Decide whether a given degree sequence permits an Euler circuit; justify with parity and connectivity.

Show a graph is bipartite by constructing a 2-coloring or citing absence of odd cycles.

Prove the handshaking lemma by counting incidences and by summing degrees.

Give a connected graph with exactly two odd-degree vertices.

Continue to Lesson 5-3 for counting principles.