×
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.

# Hamiltonian Paths

Can you draw a path that visits every node exactly once (i.e. a Hamiltonian path) on the graph above?

Is there a Hamiltonian path on the complete graph $$K_n?$$ (Note: the complete graph $$K_n$$ is the graph with $$n$$ nodes where every pair of nodes has an edge between them.)

How many Hamiltonian paths are there on the graph above?

Does the graph above have a Hamiltonian path?

True or false: all Hamiltonian paths are Eulerian paths. (Note: an Eulerian path is one that uses every edge.)

×