Discrete mathematics and graph theory · Maths EE idea · Accessible

Why greedy works for spanning trees

A research question to start from

Why do Kruskal's and Prim's algorithms always find a minimum spanning tree, and when do they give different trees?

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

Proving an algorithm correct is real mathematics, and the comparison is natural.

Mathematics you would need

Trees and cycles
Cut property
Proof by contradiction
Algorithm efficiency

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 the cut property.
Use it to prove both algorithms correct.
Discuss ties and uniqueness of the tree.

Scope and difficulty

Accessible. Accessible.

Pitfalls

Applying without proof.
Computer science focus.

Where to start reading

Search a library catalogue or a university's open lecture notes for: cut property minimum spanning tree proof Kruskal Prim. 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.