Graph Theory Fundamentals Questions and Answers

Q: If A is an adjacency matrix of a graph G, if A = AT, where AT is the transpose matrix of A, then G is :

The key's answer is A simple undirected graph.The adjacency matrix records \(a_{ij} = 1\) when there is an edge from vertex i to vertex j. If \(A = A^{T}\), then \(a_{ij} = a_{ji}\) for every pair: every edge from i to j is matched by one from j to i. That is the adjacency matrix of an undirected graph, which is what the key's option describes.Symmetry says nothing about the graph having only self loops (those are the diagonal entries) or only parallel edges, which a 0-1 adjacency matrix cannot even show. A 'general graph' would include directed graphs, whose matrices are usually not symmetric.

Q: Let G be a simple graph having no isolated vertex and having no vertex induced subgraph with exactly two edges. Then :

G is complete.Suppose two vertices \(u, w\) are not adjacent. If they had a common neighbour \(v\), the set {u, v, w} would induce a subgraph with exactly two edges. So within a connected component, any non-adjacent pair would lead along a path to such a forbidden triple; hence each component is a complete graph.If there were two components, each has an edge (no isolated vertices), and an edge from each would induce a subgraph on four vertices with exactly two edges. So G is a single complete graph.A complete graph need not be planar (\(K_{5}\)), is not self-complementary (its complement has no edges), and is a tree only when it has two vertices, so A, B and D do not hold in general.

Q: There exists a graph with vertex-connectivity \(a\), edge-connectivity \(b\) and the minimum degree \(c\), if :

Such a graph exists for \(a = 2, b = 3, c = 4\).Whitney's inequality says that for every graph, vertex connectivity \(\le\) edge connectivity \(\le\) minimum degree, i.e. \(a \le b \le c\). Moreover, Chartrand and Harary showed that every triple of positive integers with \(a \le b \le c\) is realised by some graph.Only option C satisfies \(2 \le 3 \le 4\). Option A has \(a = 4 \gt b = 2\), option B has \(a = 4 \gt b = 3\), and option D has \(b = 4 \gt c = 3\), each violating Whitney's inequality.

Q: Which of the following statements is true for a graph G ?

The true statement is that every regular graph of even degree has a 2-factor.This is Petersen's 2-factor theorem (1891): every \(2k\)-regular graph has a 2-factor, a spanning subgraph in which every vertex has degree 2. Indeed its edges can be split into \(k\) edge-disjoint 2-factors. The proof takes an Eulerian circuit of each component, orients it, and applies Hall's theorem to the resulting bipartite graph.The others fail. A graph with an odd number of vertices has no perfect matching (A). A bipartite graph with no pendant vertex need not have a 2-factor; \(K_{2,3}\) has none, since its two sides differ in size (C). And the line graph of a regular graph can have an odd number of vertices, e.g. that of \(K_{3}\) is \(K_{3}\), with no 1-factor (D).

Q: If a planar graph has v vertices, e edges and f faces, then which of the following is true ?

The true relation is v - e + f = 2.This is Euler's formula for a connected planar graph, counting the outer, unbounded face. For example, a triangle has 3 vertices, 3 edges and 2 faces (inside and outside):\[ 3 - 3 + 2 = 2 \]Option A happens to give 2 for a single cycle, where v = e, but fails for a single edge: v = 2, e = 1, f = 1 gives e + f - v = 0, while v - e + f = 2. For the triangle, option B gives 3 - 2 + 3 = 4 and option C gives 8.

Q: The thickness of a graph G is defined as minimum number of (edge-disjoint) planar subgraphs into which G can be decomposed. The thickness of G is defined as θ(G). What is the thickness of planar graph ?

The thickness of a planar graph is 1.Thickness θ(G) is the minimum number of planar subgraphs whose union is G. A planar graph can be drawn in the plane without crossings, so it is already one planar subgraph and needs no decomposition: θ(G) = 1.Thickness 2 or more is needed only for non-planar graphs. For example, \(K_{5}\) and \(K_{3,3}\) have thickness 2, because each can be split into two planar parts but not drawn as one. Values 3 and 4 belong to still larger complete graphs.

Q: What is the smallest number of colors that can be used to color the vertices of a cube so that no 2 adjacent vertices are colored identically ?

The smallest number is 2 colors.The cube's vertices can be labelled with 3-bit strings so that adjacent vertices differ in exactly one bit. Colour vertices with an even number of 1s red and those with an odd number blue: every edge changes one bit, so it always joins a red vertex to a blue one. The graph is bipartite, as the R and B labels in the figure show.One colour is impossible because the cube has edges, whose two ends would then share a colour. Three or four colours work but are not the minimum.

11.

If A is an adjacency matrix of a graph G, if A = A^T, where A^T is the transpose matrix of A, then G is :

A.A simple undirected graph
B.A graph with only self loop
C.A graph with only parallel edges
D.A general graph

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: A

The key's answer is A simple undirected graph.

The adjacency matrix records \(a_{ij} = 1\) when there is an edge from vertex i to vertex j. If \(A = A^{T}\), then \(a_{ij} = a_{ji}\) for every pair: every edge from i to j is matched by one from j to i. That is the adjacency matrix of an undirected graph, which is what the key's option describes.

Symmetry says nothing about the graph having only self loops (those are the diagonal entries) or only parallel edges, which a 0-1 adjacency matrix cannot even show. A 'general graph' would include directed graphs, whose matrices are usually not symmetric.

Discuss in Forum

12.

Let G be a simple graph having no isolated vertex and having no vertex induced subgraph with exactly two edges. Then :

A.G is planar
B.G is self-complementary
C.G is complete
D.G is a tree

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: C

G is complete.

Suppose two vertices \(u, w\) are not adjacent. If they had a common neighbour \(v\), the set {u, v, w} would induce a subgraph with exactly two edges. So within a connected component, any non-adjacent pair would lead along a path to such a forbidden triple; hence each component is a complete graph.

If there were two components, each has an edge (no isolated vertices), and an edge from each would induce a subgraph on four vertices with exactly two edges. So G is a single complete graph.

A complete graph need not be planar (\(K_{5}\)), is not self-complementary (its complement has no edges), and is a tree only when it has two vertices, so A, B and D do not hold in general.

Discuss in Forum

13.

There exists a graph with vertex-connectivity \(a\), edge-connectivity \(b\) and the minimum degree \(c\), if :

A.\(a = 4,\ b = 2,\ c = 3\)
B.\(a = 4,\ b = 3,\ c = 4\)
C.\(a = 2,\ b = 3,\ c = 4\)
D.\(a = 2,\ b = 4,\ c = 3\)

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: C

Such a graph exists for \(a = 2, b = 3, c = 4\).

Whitney's inequality says that for every graph, vertex connectivity \(\le\) edge connectivity \(\le\) minimum degree, i.e. \(a \le b \le c\). Moreover, Chartrand and Harary showed that every triple of positive integers with \(a \le b \le c\) is realised by some graph.

Only option C satisfies \(2 \le 3 \le 4\). Option A has \(a = 4 \gt b = 2\), option B has \(a = 4 \gt b = 3\), and option D has \(b = 4 \gt c = 3\), each violating Whitney's inequality.

Discuss in Forum

14.

Which of the following statements is true for a graph G ?

A.Every graph G has a perfect matching
B.Every regular graph G with even degree \(\ge 1\) has a 2-factor
C.Every bipartite graph G having no pendant vertex has a 2-factor
D.Line graph of a regular graph G has a 1-factor

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: B

The true statement is that every regular graph of even degree has a 2-factor.

This is Petersen's 2-factor theorem (1891): every \(2k\)-regular graph has a 2-factor, a spanning subgraph in which every vertex has degree 2. Indeed its edges can be split into \(k\) edge-disjoint 2-factors. The proof takes an Eulerian circuit of each component, orients it, and applies Hall's theorem to the resulting bipartite graph.

The others fail. A graph with an odd number of vertices has no perfect matching (A). A bipartite graph with no pendant vertex need not have a 2-factor; \(K_{2,3}\) has none, since its two sides differ in size (C). And the line graph of a regular graph can have an odd number of vertices, e.g. that of \(K_{3}\) is \(K_{3}\), with no 1-factor (D).

Discuss in Forum

15.

If a planar graph has v vertices, e edges and f faces, then which of the following is true ?

A.e + f - v = 2
B.e - f + v = 2
C.v + e + f = 2
D.v - e + f = 2

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

Answer: D

The true relation is v - e + f = 2.

This is Euler's formula for a connected planar graph, counting the outer, unbounded face. For example, a triangle has 3 vertices, 3 edges and 2 faces (inside and outside):

\[ 3 - 3 + 2 = 2 \]

Option A happens to give 2 for a single cycle, where v = e, but fails for a single edge: v = 2, e = 1, f = 1 gives e + f - v = 0, while v - e + f = 2. For the triangle, option B gives 3 - 2 + 3 = 4 and option C gives 8.

Discuss in Forum

16.

The travelling salesman problem can be solved using :

A.BFS traversal
B.A spanning tree
C.A minimum spanning tree
D.DFS traversal

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

Answer: C

Of the options, the travelling salesman problem is solved using a minimum spanning tree.

TSP is NP-hard, so no efficient exact method is known. For a metric TSP (distances obeying the triangle inequality), the standard approach builds a minimum spanning tree, walks it in preorder and skips repeated vertices; the resulting tour costs at most twice the optimum. Christofides' algorithm improves on this, again starting from an MST.

BFS and DFS traversals only visit vertices without regard to weights, and an arbitrary spanning tree carries no cost guarantee.

Discuss in Forum

17.

The thickness of a graph G is defined as minimum number of (edge-disjoint) planar subgraphs into which G can be decomposed. The thickness of G is defined as θ(G). What is the thickness of planar graph ?

Exam Year(s)

MH SET - 2025, SET Exam - 2025,

Answer: A

The thickness of a planar graph is 1.

Thickness θ(G) is the minimum number of planar subgraphs whose union is G. A planar graph can be drawn in the plane without crossings, so it is already one planar subgraph and needs no decomposition: θ(G) = 1.

Thickness 2 or more is needed only for non-planar graphs. For example, \(K_{5}\) and \(K_{3,3}\) have thickness 2, because each can be split into two planar parts but not drawn as one. Values 3 and 4 belong to still larger complete graphs.

Discuss in Forum

18.

What is the smallest number of colors that can be used to color the vertices of a cube so that no 2 adjacent vertices are colored identically ?

A cube drawn as an outer square joined corner to corner to an inner square; its eight vertices are labelled R and B alternately so that every edge joins an R vertex to a B vertex

A.2 colors
B.1 color
C.3 colors
D.4 colors

Exam Year(s)

MH SET - 2025, SET Exam - 2025,

Answer: A

The smallest number is 2 colors.

The cube's vertices can be labelled with 3-bit strings so that adjacent vertices differ in exactly one bit. Colour vertices with an even number of 1s red and those with an odd number blue: every edge changes one bit, so it always joins a red vertex to a blue one. The graph is bipartite, as the R and B labels in the figure show.

One colour is impossible because the cube has edges, whose two ends would then share a colour. Three or four colours work but are not the minimum.

Discuss in Forum

19.

Two graphs A and B are shown below : Which one of the following statement is true ?

Graph A is a square with both diagonals drawn, four vertices joined to each other; graph B is the drawing of a cube with eight vertices

A.Both A and B are planar.
B.Neither A nor B is planar.
C.A is planar and B is not.
D.B is planar and A is not.

Exam Year(s)

UGC NET - 2012,

Answer: A

Graph A is the complete graph on four vertices, drawn with its two diagonals crossing. It is planar, since one diagonal can be drawn outside the square without crossing the other edges. Graph B is the cube, which is also planar: drawn with one square inside the other and the corners joined, no edges cross. So both A and B are planar. The statements that neither is planar, or that only one is, are wrong. The graphs that cannot be drawn without crossings are those containing \(K_5\) or \(K_{3,3}\), which neither A nor B does. The keyed answer is the first option.

Discuss in Forum

20.

G1 and G2 are two graphs as shown :

Two graphs. G1 has six vertices a to f: a at the top, b and c on the sides, d, e and f along the base, with edges a-b, a-c, a-e, b-d, b-f, c-d, c-f, d-e and e-f. G2 has six vertices in two rows of three with many crossing edges between them.

A.Both G1 and G2 are planar graphs.
B.Both G1 and G2 are not planar graphs.
C.G1 is planar and G2 is not planar graph.
D.G1 is not planar and G2 is planar graph.

Exam Year(s)

UGC NET - 2012,

Answer: D

G1 has six vertices and nine edges, and its vertices split into two sets, a, d, f and b, c, e, with each vertex of one set joined to every vertex of the other. That is the complete bipartite graph K3,3, which is not planar by Kuratowski's theorem, so G1 is not planar. G2, as the key reads it, can be redrawn without crossing edges, so it is planar; the key is followed for G2. So G1 is not planar and G2 is planar, option (D), and the options calling G1 planar are wrong.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Graph Theory Fundamentals Questions and Answers || Graph Theory Fundamentals MCQ Questions and Answers || Graph Theory Fundamentals GK Questions and Answers || Graph Theory Fundamentals GK MCQ Questions || Graph Theory Fundamentals Multiple Choice Questions and Answers || Graph Theory Fundamentals GK || GK on Graph Theory Fundamentals || Discrete Mathematics Questions and Answers || Discrete Mathematics MCQ Questions and Answers || Discrete Mathematics GK Questions and Answers || GK on Discrete Mathematics

Graph Theory Fundamentals Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications