1
$\begingroup$

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!

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks for (1)! $\endgroup$
    – anoy
    Nov 22, 2021 at 2:51
  • $\begingroup$ For (2) then, if there exists a vertex with the strictly greatest degree, then it must be connected to the vertex with the strictly smallest degree. However, in the complement, this connection does not exist, but by definition, the two vertices should still have the greatest and smallest degrees, and thus, this is a contradiction. Is that the general idea here? $\endgroup$
    – anoy
    Nov 22, 2021 at 3:05
  • $\begingroup$ Yes, but there are two case: If there is an edge connecting them, you have shown there is a contradiction. By an identical argument you should get a contradiction if there is no edge connecting them. $\endgroup$
    – tkf
    Nov 22, 2021 at 3:09
  • $\begingroup$ I see. Thank you! $\endgroup$
    – anoy
    Nov 22, 2021 at 3:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .