Q.1 What is a graph in graph theory?
A collection of numbers
A collection of vertices and edges
A type of tree
A function
Explanation - In graph theory, a graph is defined as a set of vertices (nodes) connected by edges (lines).
Correct answer is: A collection of vertices and edges
Q.2 In an undirected graph, edges:
Have direction
Do not have direction
Always form loops
Are always weighted
Explanation - Undirected graphs have edges that do not specify direction, meaning the relationship is mutual between vertices.
Correct answer is: Do not have direction
Q.3 What is a vertex in a graph?
A line connecting two points
A point where edges meet
A loop
A graph component representing weight
Explanation - Vertices (nodes) are fundamental units in graphs that are connected by edges.
Correct answer is: A point where edges meet
Q.4 A graph with no edges is called:
Complete graph
Null graph
Cycle graph
Tree
Explanation - A null graph consists of only isolated vertices with no edges.
Correct answer is: Null graph
Q.5 Which of the following is true for a complete graph?
All vertices are isolated
Every pair of distinct vertices is connected by an edge
It has no cycles
It is always a tree
Explanation - A complete graph has edges between every pair of distinct vertices.
Correct answer is: Every pair of distinct vertices is connected by an edge
Q.6 The degree of a vertex in a graph is:
The number of edges incident to it
The number of cycles passing through it
The number of vertices connected to it
The weight of the graph
Explanation - Degree of a vertex refers to how many edges are connected to it.
Correct answer is: The number of edges incident to it
Q.7 In a directed graph, edges:
Are without direction
Have a specific direction
Always form cycles
Are always weighted
Explanation - Directed graphs consist of edges that indicate one-way relationships between vertices.
Correct answer is: Have a specific direction
Q.8 Which of the following is a simple graph?
A graph with multiple edges between two vertices
A graph with no loops or multiple edges
A graph with at least one loop
A disconnected graph only
Explanation - A simple graph does not allow loops or multiple edges between the same vertices.
Correct answer is: A graph with no loops or multiple edges
Q.9 A graph that has all vertices connected is called:
Disconnected graph
Tree
Connected graph
Cycle
Explanation - If every vertex is reachable from another, the graph is called connected.
Correct answer is: Connected graph
Q.10 The sum of degrees of all vertices in a graph is equal to:
Twice the number of edges
The number of vertices
The number of loops
The number of connected components
Explanation - By the Handshaking Lemma, the total degree equals twice the edges since each edge contributes to two vertex degrees.
Correct answer is: Twice the number of edges
Q.11 What is a path in a graph?
A sequence of edges where no vertex is repeated
A sequence of edges connecting vertices
A closed loop
An edge without a vertex
Explanation - A path connects a sequence of vertices via edges, but vertices may or may not repeat depending on context.
Correct answer is: A sequence of edges connecting vertices
Q.12 What is a cycle in a graph?
A closed path
A sequence of isolated vertices
A weighted edge
A tree
Explanation - A cycle starts and ends at the same vertex without repeating edges.
Correct answer is: A closed path
Q.13 In which type of graph do all vertices have the same degree?
Tree
Cycle graph
Regular graph
Null graph
Explanation - A regular graph has vertices with equal degree.
Correct answer is: Regular graph
Q.14 Which graph has exactly one edge between each pair of vertices?
Cycle graph
Null graph
Simple graph
Complete graph
Explanation - A complete graph connects every pair of vertices with exactly one edge.
Correct answer is: Complete graph
Q.15 What is a bipartite graph?
A graph divided into two sets of vertices with edges only between the sets
A graph with two edges for every vertex
A disconnected graph
A tree
Explanation - Bipartite graphs partition vertices into two groups, and edges only connect across groups.
Correct answer is: A graph divided into two sets of vertices with edges only between the sets
Q.16 A tree is a graph that is:
Connected and has no cycles
Disconnected and has cycles
Regular and weighted
Complete and directed
Explanation - By definition, a tree is connected and acyclic.
Correct answer is: Connected and has no cycles
Q.17 Which of the following is always true in a tree with n vertices?
It has n+1 edges
It has n-1 edges
It has n^2 edges
It has no edges
Explanation - A tree with n vertices always contains exactly n−1 edges.
Correct answer is: It has n-1 edges
Q.18 A graph that contains exactly one cycle is called:
Tree
Unicyclic graph
Bipartite graph
Null graph
Explanation - A unicyclic graph contains exactly one cycle.
Correct answer is: Unicyclic graph
Q.19 Which graph represents a real-life network of roads between cities?
Directed graph
Undirected graph
Weighted graph
Null graph
Explanation - Roads between cities often carry weights such as distances or travel times.
Correct answer is: Weighted graph
Q.20 Which graph represents one-way streets in a city?
Undirected graph
Directed graph
Complete graph
Tree
Explanation - One-way streets are modeled using directed edges in directed graphs.
Correct answer is: Directed graph
Q.21 The adjacency matrix of a graph represents:
Edges and vertices in tabular form
Only the degree of each vertex
Only cycles in the graph
Only paths in the graph
Explanation - An adjacency matrix is a square matrix showing connections (edges) between vertices.
Correct answer is: Edges and vertices in tabular form
Q.22 Which of the following graphs does not contain cycles?
Tree
Complete graph
Cycle graph
Unicyclic graph
Explanation - By definition, a tree is an acyclic connected graph.
Correct answer is: Tree
Q.23 A planar graph can be drawn on a plane:
Without edges crossing
With at least one edge crossing
With loops only
As a null graph only
Explanation - Planar graphs can be drawn in a plane such that edges do not cross.
Correct answer is: Without edges crossing
Q.24 Which theorem states that the sum of degrees of vertices is twice the number of edges?
Euler's Theorem
Handshaking Lemma
Cayley’s Formula
Hamiltonian Theorem
Explanation - The Handshaking Lemma states that the sum of degrees of all vertices is twice the number of edges.
Correct answer is: Handshaking Lemma
Q.25 A graph is said to be disconnected if:
It has no vertices
It has no edges
At least two vertices cannot be reached from each other
It contains loops
Explanation - Disconnected graphs have components where some vertices are not reachable from others.
Correct answer is: At least two vertices cannot be reached from each other