Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Theory: Complement of a Graph

  1. Nov 17, 2009 #1
    I'm wondering, is it possible a graph G and its complement G' to be complete?
  2. jcsd
  3. Nov 17, 2009 #2


    User Avatar
    Homework Helper

    Start with the complete graph [tex] K_3 [/tex], and find its complement. What do you notice? Think about the definition of the complement of a graph and think about what would happen in general.
  4. Nov 17, 2009 #3
    A complete graph G on n vertices is a graph that has an edge between any two vertices, no matter which two you pick. The complement of G is a graph of n vertices and is constructed by drawing the n vertices on the paper and then filling in the edges that are not present in G. Which edges are missing in G if G is complete?
  5. Nov 17, 2009 #4


    User Avatar
    Science Advisor
    Homework Helper

    Sure, for K_0 and K_1.
  6. Oct 13, 2010 #5
    i think you mean G union G' to be complete?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Graph Theory: Complement of a Graph
  1. Graph theory (Replies: 5)

  2. Graph theory (Replies: 10)

  3. Graph Theory (Replies: 3)

  4. Graph Theory (Replies: 1)