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

Related videos on Youtube

Max Bummer
Author by

Max Bummer

Updated on June 19, 2022

Comments

  • Max Bummer
    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
      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
      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
      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
      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
      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
      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
      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
      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
      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
      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.