- 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).
- 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.
- 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).
- 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).
An Eulerian route is about covering every edge of a graph.
To decide whether these routes exist, you only need two properties: whether the graph is connected and how many vertices have odd degree.
- 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
- 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.
- 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.
- 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.
- 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.
- 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.
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.
- 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.
- 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).
- Euler routes focus on edges.
- A different (often harder) family of questions focuses on visiting vertices.
- 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.
Do not confuse Eulerian with Hamiltonian:
- Eulerian: every edge exactly once.
- Hamiltonian: every vertex exactly once.
A route can be one, both, or neither.
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.
- 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.
- 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).
- 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.
- 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.
- 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$?