Waste less time on Facebook — follow Brilliant.
Back to all chapters

Graph Theory

Any connected group of things can be represented as a graph: cities and roads, people and friendships, and more. Learn why an even number of people have an odd number of friends.

Graph Theory - Eulerian Paths


What must be true of a path that is an Eulerian path?

True or false, if a graph has an Eulerian path then it has an Eulerian circuit.

True or false, if \(G \) is a connected graph with at least two nodes, then an Eulerian path in \( G \) must visit every node.

Two graphs \( G \) and \( G' \) each have at least one Eulerian circuit. Let \( G'' \) be a graph derived by combining both \( G \) and \( G' \) with a single edge between some node in \( G \) to some node in \( G' \). Does \( G'' \) have an Eulerian circuit?

Suppose a connected graph has 15 nodes. Given that is has an Eulerian circuit, what is the minimum number of distinct Eulerian circuits which it must have?

NOTE: A circuit uses an ordered list of nodes, so a circuit with nodes 1-2-3 is considered distinct from a circuit with nodes 2-3-1.


Problem Loading...

Note Loading...

Set Loading...