The complement of a simple graph (V, E, f) is a graph with the same set of
vertices V and with set of edges al the edges that do not appear in E. A graph is self
complementary if it is isomorphic to its complement. Denote by n the number of vertices of
the graph.
(1) Assume that a graph, is self complementary and write
$
d_1 ≤ d_2 ≤ · · · ≤ d_n−1 ≤ d_n
$
for the degrees of its vertices.
Show that $ d_i + d_{n+1-i}= n − 1 $.
(2) Assume that a graph, is self complementary and write
$
d_1 ≤ d_2 ≤ · · · ≤ d_n−1 ≤ d_n
$
for the degrees of its vertices.
Show that $ d_n = d_{n − 1} $.
I am having a bit of trouble proving these two questions, this is what I have so far:
(1) Let G be the graph and G' be its complement. The for a vertex V in G, $Degree(V_G) + Degree(V_G') = D(V_{k_n})$ where $K_n$ is the complete graph with n vertices. Thus, $d_i = (n-1) – d_i'$. And since G is self complementary, the sequence of degrees in G and G' are the same. I am not sure where I should go from here. Can I just claim that $d_i$ should be paired with $d_{n-1}$ in order to get a sum of n-1 since the smallest degree should be paired with the biggest, and the same reasoning applies to $d_2$ and $d_{n-1}$, and etc (I'm not sure if this is rigorous enough).
(2) I am a bit confused about what the question is asking here. Is it asking me to show that the last two degrees (the two biggest) are the same? If so, how should I approach this?
Thank you!
Best Answer
With $(1)$ you are almost there. From $d_i=(n-1)-d_i'$ you have: $$d_1'\geq d_2'\geq\ldots\geq d_n'.$$ As this is the same multiset as the $d_i$: $$d_n\geq d_{n-1}\geq\ldots\geq d_1,$$ we know corresponding terms must be equal: $d_i'=d_{n+1-i}$.
Substituting into your expression gives $d_i=(n-1)-d_{n+1-i}$, as required.
For $(2)$, suppose that there is an a vertex with strictly greatest degree. Then there must also be a vertex with strictly smallest degree. Is there an edge between them? It is a bit like the "I am lying" paradox, where if you are lying you must be telling the truth and vice versa.