# Graphs, line graph and complement of graph

2,880

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:
2,880 Author by

### Max Bummer

Updated on June 19, 2022

• Max Bummer less than a minute

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

• Simon Hayward over 9 years
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?
• Max Bummer over 9 years
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 :)
• Gerry Myerson over 9 years
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!
• Max Bummer over 9 years
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?
• Gerry Myerson over 9 years
@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.
• passenger over 9 years
@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...
• Max Bummer over 9 years
well when you compute that don't you get that the graph has 10 edges and not 10 nodes?
• Gerry Myerson over 9 years
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?
• Max Bummer over 9 years
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.
• Gerry Myerson over 9 years
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.