The Math Meridian
Back to 3D Geometry, Voronoi Diagrams and Graphs

Graph theory: degrees, Euler paths and minimum spanning trees

Questions at easy, medium and hard levels. Pick a level and get a fresh set every time, with instant feedback.

Useful for: IB Math AI HL

Learn it A graph has vertices joined by edges. The degree of a vertex is its number of edges. An Euler circuit (use every edge once and return) exists if every degree is even; an Euler path if exactly two degrees are odd. A minimum spanning tree connects all vertices with the least total weight (Kruskal: add the cheapest edge that doesn't make a loop).

Example: Degrees 2, 4, 3, 3, 2: Euler path or circuit?

  1. Exactly two odd degrees.
  2. An Euler path (but not a circuit).

Loading questions…