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

Directed Graphs

Is there a valid path on this directed graph from node 3 to node 1?

Note: the edges are directed toward their arrowhead (depicted as the thicker end). For example, the edge between nodes 2 and 3 is an edge from node 3 to node 2. It can only be traversed in that direction.

Yes No

Show explanation

by Brilliant Staff

How many paths of length 2 are there on this directed graph?

Note: the thicker end of an edge is an arrow head. For instance, the edge between nodes 1 and 2 signifies an edge from node 1 to node 2 (where the order is important).

Note: the length of a path is the number of edges in it.

0 2 4 6

Show explanation

by Brilliant Staff

How many distinct (undirected) graphs are there with nodes labeled 1, 2, 3, 4?

8 16 64 128

Show explanation

by Brilliant Staff

How many distinct directed graphs are there with nodes labeled 1, 2, 3, 4, 5?

Clarification: for the purpose of this question, we consider it impossible for there to be bi-directional edges. That is, for any two nodes $A$ and $B$ , there is either no edge between them, there is an edge from $A$ to $B$ , or there is an edge from $B$ to $A$ (but never both an edge from $A$ to $B$ and one from $B$ to $A$ ).

2^{10}

2^{11}

3^{10}

3^{11}

Show explanation

by Brilliant Staff

Is there a path from node 3 to node 2 on the directed graph above?

Yes No

Show explanation

by Brilliant Staff