-2
$\begingroup$

The line graph $L(G)$ of a graph $G$ is defined in the following way: the vertices of $L(G)$ are the edges of $G$, $V(L(G)) = E(G)$, and two vertices in $L(G)$ are adjacent if and only if the corresponding edges in $G$ share a vertex.

The complement of $G$ is the graph $G$ whose node set is the same as that of $G$ and whose edge set consists of all the edges that are not in $E$.

a. Find the line graph $L(G)$ for the following graph http://gyazo.com/6bda20e850e58a9e240af71cded34c63

b. Find the complement of $L(K_5)$

  • 0
    I appreciate that English is not your first language, but you really must add a bit more detail to your questions. What have you done to solve this yourself? Where are you in your studies, undergraduate?2012-11-17
  • 0
    Undergraduate and I haven't tried anything as I've read everything and don't know where to start or how to do it. That's why I am asking for any help, as much as possible :)2012-11-17
  • 2
    Where to start is with the definition. To find $L(G)$ is to find its vertices and edges. You are told its vertices are the edges of $G$ --- can you find the edges of $G$? You are told if $e_1$ and $e_2$ are vertices in $L(G)$ (hence, edges in $G$) then there is an edge joining them in $L(G)$ if and only if $e_1$ and $e_2$, as edges in $G$, share a vertex. Can you tell which pairs of edges in $G$ share a vertex? If so, then you can tell what the edges are in $L(G)$. Try it!2012-11-17
  • 0
    Where did you get the $ 5!/2!3!= 10$ Is it from the theorem that says that for any $n>=2$ $K_N$ has $n(n-1)/2$ edges? But which is its complement hence it's a linear graph?2012-11-17
  • 0
    @passenger, when you write, "has 10 nodes which are all connected," you're not suggesting, are you, that it's $K_{10}$? There are edges in $K_5$ that do not share a vertex, hence, nodes in the line graph that are not adjacent.2012-11-17
  • 0
    @GerryMyerson: no you are right. I missed a "not"... The correct is $L(K_5)$ has $10$ nodes which are not all not all connected...2012-11-18
  • 0
    well when you compute that don't you get that the graph has 10 edges and not 10 nodes?2012-11-18
  • 0
    Max, I don't understand your comment. $K_5$ has $10$ edges (and $5$ nodes). $L(K_5)$ has $10$ nodes (and $15$ edges). Any thoughts on the answer I posted?2012-11-18
  • 0
    Well yeah, that's what I was saying, it has 10 edges but how did you get to L having 10 nodes and 15 edges? No thoughts, still working on it.2012-11-19
  • 0
    From the first sentence in your post: "the vertices of $L(G)$ are the edges of $G$". So the *number* of vertices of $L$ must equal the *number* of edges of $G$, right? So that's why $L$ has 10 vertices. And, my mistake, it's not $L$ that has 15 edges, it's the *complement* of $L$ that has 15 edges.2012-11-19

2 Answers 2