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!

Homework Help: Self Complementary Graph Proof

  1. Mar 23, 2012 #1
    1. The problem statement, all variables and given/known data
    Suppose [itex]G \cong\bar{G}[/itex] and that [itex]n = |V(G)|=4k+1[/itex] for some [itex]k \ge 1[/itex]. Suppose that the degree sequence of G is [itex]d_{1}\ge d_{2} \ge ... \ge d_{n} [/itex]

    Prove that [itex]d_{i}+d_{n-i+1}=n-1[/itex] for each [itex]i=1, 2,...,n[/itex]

    2. Relevant equations
    I don't think there are any.

    3. The attempt at a solution
    I put the question in terms of k [itex]d_{i}+d_{4k-i+2}=n-1[/itex]
    and found the number of edges, since the graph has to have exactly half the maximum.
    [itex]|E(G)| = \frac{n(n-1)}{4}=\frac{(4k+1)(4k)}{4}=4k^{2}+4 [/itex]
    I'm not sure that help's, but I thought it might be useful. I need something about the degree sequence, and how it will look, but I'm not sure where to get that.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted