1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook