Discrete mathematics and graph theory · Maths EE idea · Accessible

Routes that use every street once

A research question to start from

When does a network have a route that uses every edge exactly once, and how can the shortest closed route covering every edge be found when it does not?

A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.

Why it works as a maths EE

A theorem with a short proof and an algorithm (route inspection) to analyse.

Mathematics you would need

Graphs and degrees
Eulerian circuits
Pairing odd vertices
Shortest paths

Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.

One possible line of attack

Prove Euler's condition.
Explain and justify the route-inspection algorithm.
Apply it to a network you map and evaluate it.

Scope and difficulty

Accessible. Accessible.

Pitfalls

Applying the algorithm without justifying it.
Too large a network.

Where to start reading

Search a library catalogue or a university's open lecture notes for: Euler circuit theorem proof; Chinese postman algorithm. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).

Make it your EE

Plan this EEOpens the free EE planner with this question as a starting point. Sharpen the questionSix quick checks for a focused research question. Self-check a draftCheck a section against each criterion, free.