Bissoy.com
Doctors Medicines MCQs Q&A

The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.

The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree. Correct Answer P only

The correct answer is “option 1”.

EXPLANATION:

Statement P: True

Every edge in a given cycle graph will become a vertex in the new defined graph L(G) and every vertex of the cycle graph will become an edge in the new graph.

Statement R: False

Consider a planar graph with 5 vertices and 9 edges.

Also assume, the degree of one vertex is 2 and the rest is 4.

So L(G) has 9 vertices (since G has 9 edges) and 25 edges.

But, the planar graph must satisfy the condition:

|E| < = 3|V| - 6

So for 9 vertices,

|E| < = 3×9- 6

|E| < = 21 

But L(G) has 25 edges & hence it is not planar.

So this statement is false.

Since Option 2 and 3 contains R, these options are eliminated.

Statement S: False

From this tree:

[ alt="F1 Raju Madhuri 29.05.2021 D12" src="//storage.googleapis.com/tb-img/production/21/05/F1_Raju_Madhuri_29.05.2021_D12.png" style="width: 90px; height: 84px;">

By drawing its line graph, a cycle graph can be formed of 3 vertices.

So this statement is wrong.

Hence, option 4 is wrong.

Hence, the correct answer is “option 1”.

Related Questions

Let D be a simple graph on 10 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6, a vertex of degree 7, a vertex of degree 8 and a vertex of degree 9. What can be the degree of the last vertex?
Which of the following statements regarding tree are correct? (A) All the links of a tree together does not constitute the complement of the corresponding tree (B) A connected subgraph of a connected graph is a tree if there exist (n - 1) nodes of the group (C) A connected subgraph of a connected graph is a tree if there exist many paths between any pair of nodes in it (D) The number of terminal nodes of end vertices of every tree are atleast two (E) Every connected graph has atleast one tree Choose the correct answer from the options given below: (1) (A) and (B) only (2) (B) and (C) only (3) (B) and (D) only (4) (D) and (E) only
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is 
Let G be a directed graph whose vertex set is the set of numbers from 1 to 50. There is an edge from a vertex i to a vertex j if and only if either j = i + 1 or j = 3i. Calculate the minimum number of edges in a path in G from vertex 1 to vertex 50.
There is a statement followed by two conclusions. Decide which conclusion logically follows from the given statement (s). Statement: A garden has mango, teak, neem, orange, coconut and many trees. The mango tree is 7 meters tall, the orange tree is half of its height and the coconut tree is three times the height of the mango tree. Conclusion: I. The average height of the three trees is less than 10 meters. II. The tallest tree in the garden is the coconut tree. Choose the correct option from the following. A. Only (I) follows. B. Only (II) follows. C. (I) and (II) both follow. D. Neither (I) nor (II) follows.
Horizontal clique, vertical clique and random clique are the examples of
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD .) (II) For every edge (u, v) of if u is at depth i and v is at depth j in TB , then |? − ?| = 1. Which of the statements above must necessarily be true?
In this question, two statements are given followed by two conclusions numbered i and ii. You have to assume everything in the statements to be true, then consider the two conclusions together and decide which of them logically follows beyond a reasonable doubt from the information given in the statements. Statements: Some nibs are pens. All pens are spoons. Conclusions: i) Some spoons are nibs. ii) All spoons are pens. Choose the appropriate one from the following options A) Only conclusion i follows B) Only conclusion ii follows C) Either i or ii follows D) Neither i nor ii follows and
A person wants to visit some places. He starts from a vertex and then wants to visit every vertex till it finishes from one vertex, backtracks and then explore other vertex from same vertex. What algorithm he should use?
G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE? I. If e is the lightest edge of some cycle in G, then every MST of G includes e II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e