Cutting-edge Graph Theory Test - 68+ MCQs: Graph Theory test: Challenge Your Knowledge with Graph Theory Questions and Answers

1. Which theorem states that in any graph, the sum of the degrees of all vertices is twice the number of edges?

Euler's Theorem

Handshaking Lemma

Dijkstra's Theorem

Floyd-Warshall Theorem

2. Which theorem states that in any graph, the number of vertices with odd degree is even?

Euler's Theorem

Handshaking Lemma

Pigeonhole Principle

Strong Connectivity Theorem

3. Which graph theory problem involves finding the shortest path from a source vertex to all other vertices in a weighted graph?

Hamiltonian Path Problem

Eulerian Path Problem

Dijkstra's Algorithm

Kruskal's Algorithm

4. What is the term used for a graph in which there is an edge between every pair of vertices?

Tree

Cycle

Complete Graph

Bipartite Graph

5. Which graph theory problem involves finding a subgraph that is both a tree and a spanning subgraph of a given graph?

Hamiltonian Cycle Problem

Eulerian Path Problem

Minimum Spanning Tree Problem

Bipartite Matching Problem

6. Which of the following properties does a complete bipartite graph possess?

All vertices on one side are connected to all vertices on the other side

All vertices on one side are connected to some vertices on the other side

There are no edges between vertices on the same side

Every vertex is connected to every other vertex

7. What is the term used for a set of edges connecting two sets of vertices such that no two edges have a vertex in common?

Cut Set

Matching

Bridge Set

Independent Set

8. What is the edge chromatic number of a complete graph with 'n' vertices?

n-1

n/2

9. In a bipartite graph, what does Hall's theorem state?

For every subset 'S' of the first vertex set, the neighborhood of 'S' is at least as large as 'S'.

For every subset 'S' of the second vertex set, the neighborhood of 'S' is at least as large as 'S'.

The maximum matching in the graph is equal to the minimum vertex cover.

The chromatic number is equal to the maximum degree.

10. In a tree, what is the term used for a vertex with degree 1?

Leaf

Root

Node

Branch

Graph Theory MCQ Test 5