Graph Theory MCQs | Math

By: Prof. Dr. Fazal Rehman | Last updated: February 8, 2025

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)/2 B) n2n^2 C) n(n+1)/2n(n+1)/2 D) 2n2n 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.

Leave a Comment

All Copyrights Reserved 2025 Reserved by T4Tutorials