1
$\begingroup$

I am self-studying the graph theory book by Bondy and Murty.

On page 31, the author suggests:

Every self-complementary graph on $4k + 1$ vertices has a vertex of degree $2k$.

Here what I have so far:

Given a self-complementary graph $G = (V, E)$ where $n = 4k + 1, k \geq 1$. We have $$ m = \frac{4k \cdot (4k + 1)}{4} = k \cdot (4k + 1). $$

Furthermore, let $d_G$ denote the sum of degrees of all vertices, then $$ d_G = 2k \cdot (4k + 1) = \frac{n-1}{2} \cdot n $$

So we need to prove that there must exist a vertex with the degree $(n-1)/2$, given $d_G = (n-1)/{2} \cdot n$.

Why cannot we have the degrees of all vertices different from $(n-1) / 2$, but still achieving the $(n-1) / 2$ average degree?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Because if we have more than $2k$ vertices of degree larger than $2k$, then the complement graph has more than $2k$ vertices of degree smaller than $2k$. $\endgroup$
    – Fedor Petrov
    Commented Aug 11, 2020 at 12:32
  • $\begingroup$ Such an elegant answer $\endgroup$
    – Null_Space
    Commented Aug 11, 2020 at 12:50

1 Answer 1

Reset to default
-1
$\begingroup$

As the graph is self-complementary, by definition there exists some isomorphism $f$ from the graph to its complement. Consider $f$ as a bijection from the vertex-set of the graph to itself (i.e. a permutation on the vertex-set), and consider the cycle structure of this permutation. As $4k + 1$ is odd, there must be at least one odd cycle. Every vertex in this cycle has the same degree and complementary degree, i.e. $2k$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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