First time here? Checkout the FAQ!
0 votes
The complementary graph G'  of a simple graph G has the same vertices as G. Two vertices are adjacent in G'  if and only if they are not adjacent in G. Define Qn' (Hypercube complement).

Answer given :-The graph whose vertices are bit strings of length n and two vertices are adjacent if the bit string represented by them differe by more than one bit.

I want to understand that whether the complement graph will have self loops?Because the answer given doesn't consider self loops.I mean why are we not considering the bit strings that are differing by 0 bit,as these are also not there in original graph ,so it must be in complementary graph?
asked in Graph Theory by Loyal (3.3k points)   | 44 views

The definition itself says Simple graph it can't have self loops

Simple graph: No self loop & No Multiedges between 2 vertices

Multi graph: Can have multieedges between 2 vertices but no self loop

General graph or Pseudograph: Can have both

But it was not mentioned that complement graph of simple graph has to be simple.
They are talking about 2 adjacent vertices,if there was and edge in G then it can't be there in G' .So if we take 2 vertices v1 and v2 ,if there were an edge between them in G it shouldn't be there in G'

Moreover when you do G U G' you should get complete graph. Even complete graph can't have self loop
Got it .thanks:)

Please log in or register to answer this question.

Top Users May 2017
  1. akash.dinkar12

    3152 Points

  2. pawan kumarln

    1616 Points

  3. sh!va

    1580 Points

  4. Arjun

    1336 Points

  5. Devshree Dubey

    1230 Points

  6. Angkit

    1028 Points

  7. Debashish Deka

    1012 Points

  8. Bikram

    972 Points

  9. LeenSharma

    810 Points

  10. srestha

    662 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    242 Points

  2. Ahwan

    138 Points

  3. joshi_nitish

    112 Points

  4. jjayantamahata

    104 Points

  5. Arjun

    64 Points

22,725 questions
29,056 answers
27,566 users