This graph is the graph which is told in words in below answer

Dark Mode

14,397 views

53 votes

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.

- $P$ only
- $P$ and $R$ only
- $R$ only
- $P, Q$ and $S$ only

55 votes

Best answer

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 a 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. (See below). But for a graph to be planar $|E| <= 3|V| - 6$.

For $9$ vertices $|E| \leq 3*9 - 6$

$⇒|E| \leq 27 - 6$

$⇒|E| \leq 21$. But $L(G)$ has $25$ edges and so is not planar.

As R) is False option (B), (C) are eliminated.

http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/planarity.htm

S) False. By counter example. Try drawing a simple tree which has a Root node ,Root node has one child A, node A has two child B and C. Draw its Line graph acc. to given rules in question you will get a cycle graph of $3$ vertices.

So (D) also not correct.

$\therefore$ option (**A**) is correct.

For a graph

Gwithnvertices andmedges, the number of vertices of the line graphL(G) ism, and the number of edges ofL(G) is half the sum of the squares of the degrees of the vertices inG, minusm.

**Explanation for Option R :**

G contains 5 vertices and 9 edges and in G 4 vertices of degree 4 and one vertex of degree 2.

So, in L(G) all vertices became edges. So 9 vertices and edges in L(G) we can get by first taking any single vertex of degree 4 in G. Degree 4 means 4 incident edges to vertex in G choose any 2 in C(4,2) ways and do this for 3 more vertex of degree 4. Now last 1 edge for L(G) is given by degree 2 in G.

So resulting = 4 * C(4,2) + 1

= 4 * 6 + 1

= 25 edges

Now rest you can check planarty by |E| <= 3|V|-6

0

23 votes

L(G) is a 2-set {e1,e2} of edges in G with which are adjacent to a common vertex v. This vertex v is uniquely determined by {e1,e2}.

If a vertex vv has degree d, there are (d2) 2-sets{e1,e2} such that e1 and e2 are adjacent to v

So the total number of edges in L(G) is

$\sum_{i=0}^{n}\binom{n}{2}=n(n-1)/2$

There is very simple and easy proof to drive expression for number of edges in lines graph-

edited
Oct 23, 2017
by Warrior

Just small correction

**Formula for finding no of edges in L(G):**

If a vertex v has degree d, there are C(d,2) 2-sets {e1,e2} such that e1 and e2 are adjacent to v

So the total number of edges in L(G) is

**From i=1 to n ,∑C(d _{i,}2) =∑d_{i}(d_{i}−1) / 2** ,where i is vertex and d

0

2 votes

i think

(A) P only

because by taking a simple graph of 4 vertices(i.e planar graph)(take a 2 regular graph) and we can some to know it's planar : option C eliminated ,

but tree for tree is not possible as it seems to be a cycle : option D eliminated.

also planar doesn't seem possible ,

hence possible answer is option A.