-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
    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.