Results 1 to 2 of 2

Math Help - self-complementary graph

  1. #1
    Newbie
    Joined
    Sep 2006
    From
    Edmonton, AB
    Posts
    8

    Post self-complementary graph

    A simple graph G is self-complimentary. Show there exists an integer k such that the order of G = 4k or 4k+1.

    I'm feeling a tad lost on this. I understand the idea of self-complimentary. G and its compliment will be isomorphic and have the same deg sequence, order, size.
    I have a feeling that the relation between the compliment, G and a complete graph will come in handy ie) the compliment of G= k -E(G) where k here should have subscript n for complete graph, this is a different k than in the question.

    Any thoughts on this would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by jaidon View Post
    A simple graph G is self-complimentary. Show there exists an integer k such that the order of G = 4k or 4k+1.

    I'm feeling a tad lost on this. I understand the idea of self-complimentary. G and its compliment will be isomorphic and have the same deg sequence, order, size.
    I have a feeling that the relation between the compliment, G and a complete graph will come in handy ie) the compliment of G= k -E(G) where k here should have subscript n for complete graph, this is a different k than in the question.

    Any thoughts on this would be appreciated.
    Let n>1.
    Let |V(G)|=n.
    And, |E(G)|= m

    It completment G' will have,
    |V(G')|=n
    And, |E(G)|=n(n-1)/2-m

    We require that,
    |E(G)|=|E(G')| because the graphs are isomorphic.
    Thus,
    n(n-1)/2-m=m
    Thus,
    n(n-1)/2=2m
    Thus,
    n(n-1)/4=m

    We note that m is an integer.
    Thus,
    4 divides n OR 4 divides (n-1) because gcd(n,n-1)
    Thus, n=4k or n-1=4k ---> n=4k+1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. complementary angles
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: July 16th 2010, 06:27 PM
  2. Two angles are complementary.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 21st 2010, 06:21 PM
  3. Complementary events
    Posted in the Statistics Forum
    Replies: 1
    Last Post: July 19th 2009, 01:10 PM
  4. Complementary graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 28th 2008, 05:39 AM
  5. Complementary Angles
    Posted in the Geometry Forum
    Replies: 1
    Last Post: April 15th 2008, 10:36 PM

Search Tags


/mathhelpforum @mathhelpforum