1. What is a simple graph?
A) A graph with no loops or multiple edges
B) A graph with at least one loop
C) A graph with multiple edges
D) A graph with only one vertex
2. In a connected graph, there exists at least one path between:
A) Every pair of vertices
B) Some pairs of vertices
C) Only the adjacent vertices
D) No vertices
3. The degree of a vertex in an undirected graph is:
A) The number of edges connected to it
B) Always an even number
C) Always an odd number
D) The number of cycles passing through it
4. A graph is called bipartite if:
A) It contains at least one cycle
B) It has a Hamiltonian circuit
C) Its vertices can be divided into two independent sets
D) It contains self-loops
5. The sum of the degrees of all vertices in an undirected graph is always:
A) Even
B) Odd
C) Equal to the number of edges
D) Twice the number of edges
Intermediate Graph Theory MCQs
6. A tree is a:
A) Connected graph with no cycles
B) Graph with at least one cycle
C) Complete graph
D) Graph with self-loops
7. The adjacency matrix of a graph is:
A) A representation of distances between vertices
B) A matrix showing connections between vertices
C) A list of all edges
D) The sum of all degrees
8. If a graph has ‘n’ vertices and (n-1) edges and is connected, it is:
A) A complete graph
B) A tree
C) A cycle graph
D) A bipartite graph
9. A Hamiltonian path in a graph is a path that:
A) Visits every vertex exactly once
B) Forms a cycle
C) Visits every edge exactly once
D) Has a length equal to the number of vertices
10. The shortest path problem can be solved using:
A) Kruskal’s Algorithm
B) Prim’s Algorithm
C) Dijkstra’s Algorithm
D) Bellman-Ford Algorithm
Advanced Graph Theory MCQs
11. Which of the following is true for Euler’s Theorem?
A) A connected graph has an Eulerian circuit if all vertices have even degrees
B) A connected graph has an Eulerian path if it has exactly two odd-degree vertices
C) Both A and B
D) Neither A nor B
12. A planar graph is one that:
A) Can be drawn on a plane without edges crossing
B) Has a Hamiltonian path
C) Has a complete subgraph
D) Always has a cycle
13. The chromatic number of a graph is:
A) The minimum number of colors needed to color the vertices
B) The number of edges in a cycle
C) The number of vertices in a cycle
D) The number of connected components
14. The maximum number of edges in a simple undirected graph with ‘n’ vertices is:
A)
n(n−1)/2n(n-1)/2n(n−1)/2
B)
n2n^2n2
C)
n(n+1)/2n(n+1)/2n(n+1)/2
D)
2n2n2n
15. Which algorithm is used for finding a Minimum Spanning Tree (MST)?
A) Dijkstra’s Algorithm
B) Floyd-Warshall Algorithm
C) Kruskal’s Algorithm
D) Ford-Fulkerson Algorithm
| Concept |
Definition / Explanation |
| Graph (G) |
A collection of vertices (V) and edges (E), denoted as G = (V, E). |
| Simple Graph |
A graph with no loops or multiple edges between two vertices. |
| Degree of a Vertex |
The number of edges connected to a vertex. |
| Connected Graph |
A graph in which there is a path between every pair of vertices. |
| Complete Graph (Kn) |
A graph where every vertex is connected to every other vertex. It has n(n-1)/2 edges. |
| Bipartite Graph |
A graph whose vertices can be divided into two sets, with edges only between the two sets. |
| Eulerian Circuit |
A closed path that visits every edge exactly once. Exists if all vertices have even degree. |
| Eulerian Path |
A path that visits every edge exactly once. Exists if exactly two vertices have an odd degree. |
| Hamiltonian Path |
A path that visits every vertex exactly once. |
| Hamiltonian Circuit |
A closed path that visits every vertex exactly once. |
| Planar Graph |
A graph that can be drawn on a plane without edges crossing. |
| Tree |
A connected acyclic graph with n-1 edges for n vertices. |
| Minimum Spanning Tree (MST) |
A subset of edges that connects all vertices with the minimum total edge weight. |
| Kruskal’s Algorithm |
A greedy algorithm used to find the Minimum Spanning Tree (MST) by selecting the smallest edge first. |
| Prim’s Algorithm |
A greedy algorithm for finding MST by starting from a single vertex and adding the lowest-weight edge. |
| Dijkstra’s Algorithm |
Finds the shortest path from a single source vertex to all other vertices in a weighted graph. |
| Bellman-Ford Algorithm |
Solves the shortest path problem even with negative edge weights. |
| Floyd-Warshall Algorithm |
A dynamic programming algorithm to find the shortest paths between all pairs of vertices. |
| Adjacency Matrix |
A matrix representation of a graph, where entry (i, j) is 1 if an edge exists between vertices i and j. |
| Adjacency List |
A list representation where each vertex has a list of connected vertices. |
| Chromatic Number |
The minimum number of colors needed to color a graph so that no two adjacent vertices share the same color. |
| Graph Isomorphism |
Two graphs are isomorphic if they have the same structure, regardless of labeling. |
| Max Edges in a Simple Graph |
For n vertices, the maximum edges in a simple undirected graph is n(n-1)/2. |
