2
$\begingroup$

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?

  1. The line graph of a cycle is a cycle.
  2. The line graph of a clique is a clique.
  3. The line graph of a planar graph is planar.
  4. The line graph of a tree is a tree.

I have already done the following:

  1. The line graph of a cycle is a cycle.

  2. [See below.]

  3. The line graph of a planar graph is planar. Proof by counter-example: Let $G$ have $5$ vertices and $9$ edges which is a planar graph but $L(G)$ isn't a planar graph because then it will have $25$ edges; therefore, $|E|\leq 3\cdot|V|-6$ is violated.

  4. The line graph of a tree is a tree. By counter-example: Try drawing a simple tree which has a root node. The root node has one child $A$ and node $A$ has two children $B$ and $C$. Draw its line graph according to given rules in question and you will get a cycle graph of $3$ vertices.

My doubt is that I can't figure out 2. The line graph of a clique is a clique. Please help me out here.

$\endgroup$
  • $\begingroup$ In your example for (R) are you sure $L(G)$ has $25$ edges? I only count $24$ (which is enough). Anyway isn't the star graph $K_{1,5}$ a simpler example? The line graph is $K_5$ which is not planar. As for (Q) what is the line graph of $K_4$? Can't you find two edges in $K_4$ which have no common vertex? $\endgroup$ – bof Aug 19 '19 at 6:47
  • $\begingroup$ Yes it will have 25 edges using this formula math.stackexchange.com/questions/301490/… $\endgroup$ – John Lucas Aug 19 '19 at 6:49
  • $\begingroup$ The line graph of a clique will be a clique iff every two edges of the clique are adjacent. Are they? $\endgroup$ – Matthew Daly Aug 19 '19 at 7:02
  • 1
    $\begingroup$ @JohnLucas According to that formula the number of edges in $L(G)$ is $$\frac{4\cdot3}2+\frac{4\cdot3}2+\frac{4\cdot3}2+\frac{3\cdot2}2+\frac{3\cdot2}2=6+6+6+3+3=24.$$ $\endgroup$ – bof Aug 19 '19 at 7:33
  • 1
    $\begingroup$ @JohnLucas There is no such graph. Did you try to draw it? If there are $5$ vertices, each vertex of degree $4$ must be joined to all the other vertices, including your supposed vertex of degree $2$. No, there is (up to isomorphism) only one (simple) graph with $5$ vertices and $9$ edges; it's the graph you get by removing one edge from the clique $K_5$; its degree sequence is $4,4,4,3.3$ (the endpoints of the missing edge lose one degree); and its line graph has $24$ edges. $\endgroup$ – bof Aug 20 '19 at 9:26
1
$\begingroup$

HINT: Let $G$ be a clique on the $n$ vertices $\{x_1,x_2,\ldots, x_n\}$ for $n \ge 4$. Then edges $e_1 = x_1x_2$ and $e_2=x_3x_4$ do not share a vertex. So are $v(e_1)$ and $v(e_2)$ adjacent to each other in $L(G)$?

If you want to look at this another way, $L(K_n)$ has $\frac{n(n-1)}{2}$ vertices. But for each $e \in K_n$, the vertex $v(e)$ has degree only $2(n-2)$ [make sure you see why]. Note that $\frac{n(n-1)}{2} - 1$ $>>$ $2(n-2)$ for $n > 6$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.