Graphs

• Graphs are made of vertices (nodes) connected by edges (arcs) — the building blocks of everything else in this chapter.
• A walk, path, trail, cycle, and tour are all different types of "route" through a graph, distinguished by whether they repeat vertices or edges.
• Graphs come in types: connected, complete (K_n), weighted (network), directed (digraph), simple, and planar.
• A tree is a connected graph with no cycles; a spanning tree covers every vertex of the original graph using the minimum number of edges needed to stay connected.
• The degree (valency) of a vertex counts its edges. Euler's handshaking lemma says the total degree always equals 2 × (number of edges), and the number of odd vertices is always even.
• A graph is Eulerian if it has a closed trail using every edge exactly once (needs all-even degrees); semi-Eulerian if it has an open one (needs exactly two odd vertices).
• A Hamiltonian graph visits every vertex exactly once and returns to the start; semi-Hamiltonian does the same but doesn't return.
• The planarity algorithm uses a Hamiltonian cycle to test whether a graph can be redrawn with no crossing edges.

  Vertices and Edges

Think of a graph the way you'd think of a subway map. The stations are vertices (also called nodes) — they can represent objects, places, or people. The train lines connecting stations are edges (also called arcs) — they represent a connection between two vertices.

Some vocabulary you need to be precise about:

• Adjacent vertices — two vertices directly joined by an edge.
• Adjacent edges — two edges that share a common vertex.
• Loop — an edge that starts and ends at the vertex (like a train line that leaves a station and comes straight back).
• Multiple edges — more than one edge connecting the same pair of vertices is allowed.

Notice: edges BC and CE are adjacent (they share vertex C). Edge DD is a loop.

  Walks, Paths, Trails, Cycles & Tours

This is the part students mix up the most — five words that all mean "a route through the graph," but each with one specific rule attached. Here's the trick: think of them as a family, from to .