-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

2

Concerning the complement of $L(K_5)$, here are some thoughts:

  1. Given any edge $e$ in $K_5$, show that there are exactly $3$ edges in $K_5$ that don't share a vertex with $e$.

  2. Call those three edges $a,b,c$, and notice that any two of them share a vertex.

  3. Deduce that every vertex $v$ of $L(K_5)$ has degree $3$, and that the $3$ vertices of $L(K_5)$ that are adjacent to $v$ are not adjacent to each other.

  4. I have a feeling you might want to familiarize yourself with the Petersen graph.

0

The complement of the line graph of $K_5$ can be constructed as follows. Label the vertices of $K_5$ as $1,2,\ldots,5$. The 10 edges of this graph are the ${5 \choose 2}$ 2-subsets of $\{1,\ldots,5\}$. The line graph $L(K_5)$ thus has 10 vertices, labeled by these 10 2-subsets $\{i,j\}$. Two vertices $\{i,j\}, \{k,\ell\}$ are adjacent in $L(K_5)$ iff the two 2-subsets have a nontrivial overlap. The complement of $L(K_5)$ is the graph with the same 10 vertices, and with two vertices being adjacent iff the corresponding two 2-subsets are disjoint. This graph is the famous Petersen graph (common drawings of this graph are available online) and happens to arise often as a counterexample to many conjectures.

More generally, the generalized Kneser graph $J(n,k,i)$ is the graph whose vertex set is the set of all $k$-subsets of $\{1,\ldots,n\}$, and with two vertices adjacent iff the corresponding subsets have an intersection of size exactly $i$. Thus, $J(5,2,1)$ is $L(K_5)$, and its complement graph $J(5,2,0)$ is the Petersen graph.