Question 10684 –
February 13, 2024Question 8785 –
February 13, 2024Question 8763 –
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.
| A | P only P and R only R only P, Q and S only Question 33 Explanation: P) True. Because every edge in cycle graph will become a vertex in new graph L(G) and every vertex of cycle graph will become an edge in new graph. R) False. We can give counter example. Let G has 5 vertices and 9 edges which is planar graph. Assume degree of one vertex is 2 and of all others are 4. Now, L(G) has 9 vertices (because G has 9 edges) and 25 edges. But for a graph to be planar, |E| ≤ 3|v| – 6 For 9 vertices |E| ≤ 3 × 9 – 6 ⇒ |E| ≤ 27 – 6 ⇒ |E| ≤ 21. But L(G) has 25 edges and so is not planar. As (R) is false, option (B) & (C) are eliminated. Correct Answer: A Question 33 Explanation: P) True. Because every edge in cycle graph will become a vertex in new graph L(G) and every vertex of cycle graph will become an edge in new graph. R) False. We can give counter example. Let G has 5 vertices and 9 edges which is planar graph. Assume degree of one vertex is 2 and of all others are 4. Now, L(G) has 9 vertices (because G has 9 edges) and 25 edges. But for a graph to be planar, |E| ≤ 3|v| – 6 For 9 vertices |E| ≤ 3 × 9 – 6 ⇒ |E| ≤ 27 – 6 ⇒ |E| ≤ 21. But L(G) has 25 edges and so is not planar. As (R) is false, option (B) & (C) are eliminated. |
| ∀x(∃z(¬β)→∀y(α)) | |
| ∀x(∀z(β)→∃y(¬α)) | |
| ∀x(∀y(α)→∃z(¬β)) | |
| ∀x(∃y(¬α)→∃z(¬β)) |