- Networks (graphs) give a powerful way to model journeys, routes, and connections.
- In this section you learn to classify paths, cycles, and special routes that use edges or vertices in controlled ways.
- These ideas underpin problems such as planning a postal delivery route (the Chinese Postman Problem) and planning a shortest "visit-everywhere-once" tour (the Traveling Salesman Problem).
Paths, Trails, And Cycles Describe Different Kinds Of Journeys
- A path is a sequence of vertices where consecutive vertices are joined by an edge.
- Depending on the context, we care about whether edges or vertices are repeated.
Definition
Trail
A walk through a graph that does not repeat any edge.
Definition
Cycle
A path that starts and ends at the same vertex and does not pass through any vertex more than once.
- A cycle is a special type of closed path.
- Cycles are important because many real-world routes must return to the start (for example, a delivery van that must return to the depot).
Note
- Different textbooks sometimes use slightly different conventions for the words walk, path, and trail.
- In this topic, the key distinction is whether an edge is repeated (trail) and whether the route returns to its start without repeating vertices (cycle).
Euler Routes Are About Using Every Edge
An Eulerian route is about covering every edge of a graph.
Definition
Eulerian circuit
A trail that uses every edge exactly once and ends at the starting vertex.
Definition
Eulerian trail
A trail that uses every edge exactly once but starts and ends at different vertices.
To decide whether these routes exist, you only need two properties: whether the graph is connected and how many vertices have odd degree.
Traversability Depends On Odd Vertices
- A graph is called traversable if you can draw it without lifting your pen and without retracing an edge.
- A connected graph:
- with only even-degree vertices is traversable and has an Eulerian circuit (you can start anywhere and finish where you started)
- with exactly two odd-degree vertices is traversable and has an Eulerian trail (any such trail must start at one odd vertex and finish at the other)
- with more than two odd-degree vertices has no Eulerian circuit or Eulerian trail, so it is non-traversable without repeating edges
Example
- A connected graph has vertex degrees: 2, 2, 4, 4, 3, 3.
- There are exactly two odd degrees (the 3s), so an Eulerian trail exists.
- Any Eulerian trail must start at one of the degree-3 vertices and end at the other.
Common Mistake
- Students often count degree incorrectly at junctions where two edges overlap visually.
- Always count edges meeting at the vertex, not the number of "directions" you can travel.
Why Odd Vertices Matter (Intuition)
- Each time you enter a vertex along an edge in a trail, you also leave along a different unused edge.
- That pairs edges up at the vertex.
- Pairing is only possible if the degree is even, except possibly at the start and finish of an open trail.
Analogy
- Think of each edge as one sock.
- To pass through a vertex without stopping, you need to match socks into pairs (enter, leave).
- Even degree means perfect pairing.
- Odd degree leaves one unpaired sock, which can only happen at the start or end of the journey.
The Chinese Postman Idea: When You Must Repeat Edges
- Many applications require you to travel every edge at least once, such as checking every corridor in a building or sweeping every street in an area.
- If the graph is not already Eulerian, you have to repeat (duplicate) some edges.
Definition
Chinese postman problem
The problem of finding a shortest closed route that traverses every edge of a weighted graph at least once.
The Key Strategy: Pair Up Odd Vertices
If a connected weighted graph has $2k$ odd vertices, you must make all degrees even by duplicating edges so the final route can be an Eulerian circuit.
A standard strategy is:
- List the odd-degree vertices.
- Find the shortest path distance between each pair of odd vertices.
- Choose pairings of odd vertices that give the minimum total added distance.
- Duplicate the edges along those chosen shortest paths.
- Find an Eulerian circuit on the new (augmented) network.
Note
- Every time you duplicate an edge, the degrees of its two endpoints increase by 1.
- This is exactly what you need to turn odd degrees into even degrees.
Exam technique
- In exam questions, you are often asked to justify "why at least ___ edges must be doubled."
- The quickest argument is: count the odd vertices.
- If there are $2k$ odd vertices, you need at least $k$ pairings, which forces at least $k$ routes between odd vertices to be duplicated (sometimes more than $k$ edges, depending on the shortest paths).
Hamilton Routes Are About Visiting Every Vertex Once
- Euler routes focus on edges.
- A different (often harder) family of questions focuses on visiting vertices.
Definition
Hamiltonian path
A path that visits every vertex exactly once.
Definition
Hamiltonian cycle
A Hamiltonian path that returns to its starting vertex.
- Unlike Eulerian routes, there is no simple degree test that always tells you whether a Hamiltonian cycle exists.
- Some graphs clearly have one, others clearly do not, but for complicated graphs there is, in general, no quick method to decide.
Common Mistake
Do not confuse Eulerian with Hamiltonian:
- Eulerian: every edge exactly once.
- Hamiltonian: every vertex exactly once.
A route can be one, both, or neither.
Recognizing When A Hamiltonian Cycle Cannot Exist
Although there is no single universal test, you can often prove impossibility by using structural reasoning.
Common ideas include:
- Cut vertex (articulation point): if removing a vertex disconnects the graph, a Hamiltonian cycle is often impossible because the cycle would need to pass through that vertex twice to reach both sides.
- Bridge: an edge whose removal disconnects the graph cannot lie on a Hamiltonian cycle, because a cycle would need an alternative way around.
- Too few connections: if a vertex has degree 1, a Hamiltonian cycle is impossible, because a cycle would have to enter and leave that vertex.
Hint
- To check a possible Hamiltonian cycle, mark each vertex as you visit it.
- The moment you are forced to revisit a vertex or get stuck before visiting all vertices, that attempt fails.
The Traveling Salesman Problem Is A Shortest Hamiltonian Cycle Problem
- In the Traveling Salesman Problem (TSP) you are given "cities" and distances between every pair, and you want the shortest round trip that visits each city once.
- In graph language, this is: find the shortest Hamiltonian cycle in a weighted graph (often a complete graph).
Definition
Complete graph
A graph where every pair of distinct vertices is joined by an edge.
Example
Building A Network From A Court Outline
- Many network problems start with geometry: you measure or calculate lengths, then use them as edge weights.
- Suppose a court has straight sides and semicircular ends.
- To weight the edges around the boundary you might need:
- arc lengths of the semicircles
- straight-line distances between junctions and corners
- If a semicircle has diameter $d$, then its arc length is half a circumference: $$\text{semicircle arc length} = \frac{1}{2}(\pi d)=\pi\left(\frac d2\right)$$
- If you need the shortest distance from an arc to a corner, that is often a straight line and can be found using right-triangle geometry (typically Pythagoras) once you identify the relevant radii and perpendiculars.
Exam technique
- In "geometry to network" questions, draw and label the geometry first.
- Only then simplify to a graph by choosing junctions as vertices and using calculated lengths as edge weights.
Self review
- A connected graph has 0 odd vertices. What special route must exist?
- A connected graph has exactly 2 odd vertices. Where must an Eulerian trail start and finish?
- In one sentence, state the difference between Eulerian and Hamiltonian.
- Why does the number of Hamiltonian cycles in a complete graph grow so quickly with $n$?
