Graph Theory Quiz

What is a multigraph?

• A graph with no edges

• A graph with only loops

• A graph with only one edge between nodes

• A graph with multiple edges between nodes

What defines a bipartite graph?

• It has two sets of vertices with edges only between the sets

• It has no vertices

• It has edges only within a single set of vertices

• It contains odd cycles

What is the chromatic number of a bipartite graph?

• 2

• 1

• 3

• 4

What is a complete bipartite graph?

• A graph where every vertex in set X connects to every vertex in set Y

• A graph with only one edge

• A graph with no edges

• A graph with only loops

What is the maximum number of edges in a bipartite graph with n vertices?

• (1/2)*n^2

• n^2

• n

• (1/4)*n^2

What is a property of bipartite graphs?

• They have no vertices

• They are 2 colorable

• They contain odd cycles

• They can have loops

What is the chromatic number of a complete graph?

• 1

• 2

• Equal to the number of vertices

• 0

What is a spanning tree?

• A tree that connects all vertices with the minimum number of edges

• A graph with no vertices

• A disconnected graph

• A tree with cycles

What does the Depth-First Search (DFS) algorithm do?

• Does not use any data structure

• Visits all vertices in a random order

• Explores all branches of a graph as far as possible before backtracking

• Only visits the first vertex

What is the purpose of graph coloring?

• To find the shortest path

• To create a visual representation of the graph

• To remove edges from the graph

• To assign colors to vertices so that no two adjacent vertices share the same color