Graph Theory

Concept Quizzes

Tracing Paths
Complete Graphs
Graph Theory - Eulerian Paths
Hamiltonian Paths
Trees
Bipartite Graphs
Planar Graphs
Directed Graphs

Challenge Quizzes

Graph Theory: Level 1 Challenges
Graph Theory: Level 2 Challenges
Graph Theory: Level 3 Challenges
Graph Theory: Level 5 Challenges

Graph Theory - Eulerian Paths

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

It uses every edge at most once It uses every edge exactly once It uses every edge at least once

Show explanation

View wiki

by Brilliant Staff

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

True False

Show explanation

View wiki

by Brilliant Staff

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

False True

Show explanation

View wiki

by Brilliant Staff

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?

There exist graphs for which no matter the nodes the edge is attached to, yes For a certain pair of graphs connected by an edge attached to certain nodes, yes No, it is impossible Regardless of the graphs and the nodes to which the edge is added, yes

Show explanation

View wiki

by Brilliant Staff

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.

15 45 1 30

Show explanation

View wiki

by Brilliant Staff