Preparing for your Bihar Engineering University (BEU) Graph Theory exam?
You’re in the right place! We have compiled and solved every objective question (Question 1) from the 2022, 2023, and 2024 previous year question papers.
Use this guide to test your knowledge, understand key concepts, and master the types of questions you’ll face.
Table of Contents
B.Tech 6th Semester Examination, 2024
Here are the multiple-choice questions from the 2024 paper.
Q.1 (a): Let G be a graph with 10 edges. The number of edges of its dual graph is
(i) 2
(ii) 6
(iii) 8
(iv) 10
Answer: (iv) 10
Explanation: A fundamental property of dual graphs is that a graph and its dual always have the same number of edges.
Q.1 (b): Which of the following is true, if n is the number of vertices m is the number of edges and f is the number of faces of a connected plane graph.
(i) n + m + f = 2
(ii) n – m – f = 2
(iii) n – m + f = 2
(iv) n + m – f = 2
Answer: (iii) n – m + f = 2
Explanation: This is Euler’s formula for connected planar graphs.
Q.1 (c): Which of the following graphs is planar?
(i) K5
(ii) K4,2
(iii) K3,3
(iv) K6
Answer: (ii) K4,2
Explanation: K5 and K3,3 are the two basic non-planar graphs. K6 contains K5 as a subgraph so it is non-planar. K4,2 can be drawn without edge crossings and is planar.
Q.1 (d): The chromatic number of the Petersen graph is
(i) 3
(ii) 4
(iii) 5
(iv) None of the above
Answer: (i) 3
Explanation: This is a standard property of the Petersen graph.
Q.1 (e): Eigen values of a real symmetric matrix are always
(i) Positive
(ii) Negative
(iii) Real
(iv) Complex
Answer: (iii) Real
Explanation: A fundamental theorem of linear algebra: eigenvalues of real symmetric matrices are real. The adjacency matrix of an undirected graph is real and symmetric.
Q.1 (f): Let G be a simple planar graph on 10 vertices with 15 edges. If G is a connected graph, then the bounded faces in any embedding of G on the plane is
(i) 6
(ii) 7
(iii) 23
(iv) 8
Answer: (i) 6
Explanation: Use Euler’s formula v – e + f = 2. Given v = 10 and e = 15. 10 – 15 + f = 2 => f = 7. Total faces = 7, so bounded faces = 7 – 1 = 6.
Q.1 (g): Euler Formula applies to….
(i) All graphs
(ii) All complete graphs
(iii) All bipartite graphs
(iv) All connected planar graphs
Answer: (iv) All connected planar graphs
Explanation: Euler’s formula v – e + f = 2 holds for connected planar graphs.
Q.1 (h): The maximum degree of any vertex in a simple graph with n vertices is
(i) 2n + 1
(ii) n + 1
(iii) n – 1
(iv) n
Answer: (iii) n – 1
Explanation: In a simple graph (no loops or multiple edges), a vertex can be connected to all other vertices: n – 1.
Q.1 (i): Degree of any vertex of a graph is
(i) Number of vertices in a graph
(ii) The number of edges incident with the vertex
(iii) Number of edges in a graph
(iv) Number of vertices adjacent to that vertex
Answer: (ii) The number of edges incident with the vertex
Explanation: This is the definition of degree. (Note: for loops count twice.)
Q.1 (j): The complete graph with 4 vertices has k edges where k is
(i) 3
(ii) 4
(iii) 5
(iv) 6
Answer: (iv) 6
Explanation: Number of edges in complete graph K_n is n(n – 1)/2. For n = 4, edges = 4 * 3 / 2 = 6.
B.Tech 8th Semester Examination, 2024 (Special)
Here are the multiple-choice questions from the 2024 Special paper.
Q.1 (a): What is a graph in graph theory?
(i) A type of chart
(ii) A collection of vertices and edges
(iii) A type of table
(iv) A type of diagram
Answer: (ii) A collection of vertices and edges
Explanation: Fundamental definition of graph.
Q.1 (b): Spanning trees are sub-graphs that
(i) Connect all vertices without cycles
(ii) Connect some vertices with cycles
(iii) Connect all vertices with cycles
(iv) Are disconnected
Answer: (i) Connect all vertices without cycles
Explanation: A spanning tree includes all vertices and is a tree (connected, no cycles).
Q.1 (c): The Traveling Salesman Problem is associated with
(i) Finding shortest paths between all nodes
(ii) Finding Hamiltonian circuits
(iii) Coloring graphs
(iv) Checking for isomorphism
Answer: (ii) Finding Hamiltonian circuits
Explanation: TSP seeks the minimum-weight Hamiltonian circuit in a weighted graph.
Q.1 (d): Which of the following is a null graph?
(i) A graph with no vertices
(ii) A graph with no edges
(iii) A graph with a single vertex
(iv) A graph with infinite edges
Answer: (ii) A graph with no edges
Explanation: A null (edgeless) graph has vertex set V and empty edge set.
Q.1 (e): The rank of a cut set is
(i) Number of edges in the set
(ii) Degree of the graph
(iii) Number of connected components after removal
(iv) None of the above
Answer: (iv) None of the above
Explanation: The usual meaning of “rank” in this context is rank of the cut-set matrix; rank of an individual cut-set is not a standard term. So none of the given options correctly describe that rank.
Q.1 (f): A planar graph is one that
(i) Can be drawn on a plane without edges crossing
(ii) Has no cycles
(iii) Has a fixed number of vertices
(iv) Is disconnected
Answer: (i) Can be drawn on a plane without edges crossing
Explanation: Definition of planar graph.
Q.1 (g): The incidence matrix of a bipartite graph
(i) Always symmetric
(ii) Never symmetric
(iii) Contains negative values
(iv) None of the above
Answer: (iv) None of the above
Explanation: Incidence matrices are generally not symmetric. They contain negative entries only for directed graphs. Since none of the listed options are strictly correct for an undirected bipartite graph, “None of the above” is appropriate.
Q.1 (h): For a cycle graph Cn, where n is odd, the chromatic number is
(i) 1
(ii) 2
(iii) 3
(iv) n
Answer: (iii) 3
Explanation: An odd cycle requires 3 colors.
Q.1 (i): Which matrix is used to represent a directed graph?
(i) Incidence matrix
(ii) Adjacency matrix
(iii) Path matrix
(iv) All of the above
Answer: (iv) All of the above
Explanation: All these matrices can represent directed graphs (with appropriate definitions).
Q.1 (j): A directed graph with no cycles is called
(i) A tree
(ii) A bipartite graph
(iii) An acyclic digraph
(iv) A complete graph
Answer: (iii) An acyclic digraph
Explanation: Definition of directed acyclic graph (DAG).
End Semester Examination – 2023
This paper’s compulsory Question 1 consisted of short-answer definitions.
Q.1 (a): Define a Graph.
Answer: A graph G is an ordered pair (V, E), where V is a non-empty set of vertices (or nodes) and E is a set of edges connecting pairs of vertices.
Q.1 (b): List three situations where a graph could prove useful.
Answer: 1. Social networks: users as vertices and friendships as edges. 2. Navigation systems: cities/intersections as vertices and roads as weighted edges. 3. Computer networks: computers/routers as vertices and connections as edges.
Q.1 (c): Define walk with respect to graph.
Answer: A walk is an alternating sequence of vertices and edges v0, e1, v1, e2, …, ek, vk where each edge ei is incident to vertices vi-1 and vi. Vertices and edges may repeat.
Q.1 (d): What is degree (valency) of a vertex?
Answer: Degree of a vertex is the number of edges incident to it. A loop at a vertex counts twice.
Q.1 (e): When are two edges and vertices said to be adjacent?
Answer: Adjacent vertices: two vertices are adjacent if they are connected by an edge. Adjacent edges: two edges are adjacent if they share a common vertex.
Q.1 (f): State the necessary conditions to show that two graphs are isomorphic.
Answer: They must have the same number of vertices, the same number of edges, and the same degree sequence (that is, the same multiset of vertex degrees).
Q.1 (g): What are Euler trail and Euler circuit?
Answer: An Euler trail (path) visits every edge exactly once. An Euler circuit is an Euler trail that starts and ends at the same vertex.
Q.1 (h): Define a Euler Graph.
Answer: A Euler graph contains an Euler circuit. A connected graph is Eulerian iff every vertex has even degree.
Q.1 (i): What is colouring problem?
Answer: Assigning colors to vertices so that adjacent vertices have different colors. The goal often is to minimize the number of colors (the chromatic number).
Q.1 (j): Define elementary tree transformation?
Answer: Transform one spanning tree into another by adding a single chord (creating a cycle) and then removing one of the original tree edges from that cycle.
Q.1 (k): What is meant by fundamental cut-set?
Answer: With respect to a spanning tree T, a fundamental cut-set is formed by exactly one branch of T and the set of chords that connect across that branch.
Special Examination – 2023
This paper also featured short-answer definitions for its compulsory Question 1.
Q.1 (a): Define edge connectivity.
Answer: Edge connectivity is the minimum number of edges whose removal disconnects the graph.
Q.1 (b): What is meant by an arbitrarily traceable graph?
Answer: A graph that has an Euler trail. A connected graph is arbitrarily traceable if it has zero or exactly two vertices of odd degree.
Q.1 (c): What is meant by shortest distance arborescence?
Answer: An arborescence (a directed rooted tree) in a weighted directed graph such that the path from the root to every other vertex is the shortest possible.
Q.1 (d): What is meant by an invariant of a graph? Give examples.
Answer: An invariant is a property preserved under isomorphism. Examples: number of vertices, number of edges, degree sequence.
Q.1 (e): Define walk, path and circuit with examples.
Answer: Walk: sequence with possible repetition (e.g., A-B-C-B). Path: walk with no repeated vertices. Circuit: closed walk (start = end) with no repeated intermediate vertices.
Q.1 (f): Define planar graph and non-planar graph with examples.
Answer: Planar graph: can be drawn in plane without edge crossings (e.g., K4). Non-planar graph: cannot be drawn without crossings (e.g., K5).
Q.1 (g): Define fundamental circuits and fundamental cut-sets.
Answer: Fundamental circuit: cycle formed by adding one chord (edge not in the spanning tree) to a spanning tree. Fundamental cut-set: cut-set formed by one branch of a spanning tree together with chords crossing it.
Q.1 (h): Define chromatic number. What is the chromatic number of a tree with two or more vertices?
Answer: Chromatic number is the minimum number of colors needed to color vertices so adjacent vertices differ. Chromatic number of any tree with two or more vertices is 2.
Q.1 (i): State Kruskal’s Algorithm. Give its advantages.
Answer: Kruskal: sort edges by increasing weight, then add edges one-by-one if they don’t form a cycle until MST built. Advantage: simple and efficient, especially for sparse graphs.
Q.1 (j): Define the cut-vertex and connectivity.
Answer: Cut-vertex: vertex whose removal increases the number of connected components. Vertex connectivity: minimum number of vertices whose removal disconnects the graph (or reduces it to a single vertex).
B.Tech 6th Semester Exam., 2022
Here are the multiple-choice questions from the 2022 paper.
Q.1 (a): What is the number of edges present in a complete graph having n vertices?
(i) (n * (n + 1)) / 2
(ii) n
(iii) (n * (n – 1)) / 2
(iv) Information given is insufficient
Answer: (iii) (n * (n – 1)) / 2
Explanation: Each vertex connects to n – 1 others but each edge counted twice, so n(n – 1)/2.
Q.1 (b): A connected planar graph having 6 vertices, 7 edges contains __ regions.
(i) 17
(ii) 9
(iii) 3
(iv) 13
Answer: (iii) 3
Explanation: v – e + f = 2 => 6 – 7 + f = 2 => f = 3.
Q.1 (c): Which of the following properties does a simple graph not hold?
(i) Must be unweighted
(ii) Must have no multiple edges
(iii) Must have no loops or multiple edges
(iv) Must be connected
Answer: (iv) Must be connected
Explanation: Simplicity requires no loops or multiple edges, but connectivity is not required.
Q.1 (d): For a given graph G having v vertices and e edges which is connected and has no cycle, which of the following statements is true?
(i) v = e + 1
(ii) v = e
(iii) v + 1 = e
(iv) v = e – 1
Answer: (i) v = e + 1
Explanation: A connected acyclic graph is a tree so e = v – 1, rearranged v = e + 1.
Q.1 (e): The time complexity to calculate the number of edges in a graph whose information is stored in the form of an adjacency matrix is
(i) O(E)
(ii) O(V^2)
(iii) O(E^2)
(iv) O(V)
Answer: (ii) O(V^2)
Explanation: An adjacency matrix is V x V, so you examine on order V^2 entries.
Q.1 (f): In a given connected graph G, what is the value of rad(G) and diam(G)?
(i) 2, 3
(ii) 2, 2
(iii) 3, 2
(iv) 3, 3
Answer: Not Answerable
Explanation: No graph was provided; cannot determine radius and diameter without the graph.
Q.1 (g): The column sum in an incidence matrix for a directed graph having no self-loop is
(i) 1
(ii) 0
(iii) 2
(iv) 3
Answer: (ii) 0
Explanation: Each directed edge column has +1 at the tail and -1 at the head, summing to 0.
Q.1 (h): A graph structured stack is a/an
(i) undirected graph
(ii) regular graph
(iii) directed graph
(iv) directed acyclic graph
Answer: (iv) directed acyclic graph
Explanation: The graph-structured stack (GSS) used in parsing is a DAG.
Q.1 (i): Graph structured stack finds its application in
(i) Todd-Coxeter algorithm
(ii) Heap sort
(iii) Bogosort
(iv) Tomita’s algorithm
Answer: (iv) Tomita’s algorithm
Explanation: GSS is used in Tomita’s generalized LR parsing algorithm.
Q.1 (j): What is the number of vertices of degree 2 in a path graph having n vertices where n > 2?
(i) n
(ii) n – 2
(iii) 0
(iv) 2
Answer: (ii) n – 2
Explanation: A path has two endpoints of degree 1; the remaining n – 2 internal vertices have degree 2.