# Graphs, line graph and complement of graph

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)$

-
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? – Simon Hayward Nov 17 '12 at 9:52
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 :) – Max Bummer Nov 17 '12 at 11:15
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! – Gerry Myerson Nov 17 '12 at 11:31
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? – Max Bummer Nov 17 '12 at 13:56
@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. – Gerry Myerson Nov 17 '12 at 21:55

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.

-

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.

-