Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

share|cite|improve this question
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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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