looking for a better way to prove basic graph theory result.

Question

Let G be a self-complementary graph of order $n \equiv 1$ (mod 4).

Show that G has an odd number of vertices of degree $\frac{n-1}{2} $

First we know that $n= 4k+1$ also we have an even number of odd vertices and by the fact that G is self complimentary we have an even number of paired even vertices. even + even is even the only remaining vertices are self complimentary i.e vertices of the form $4k−d =d$ since n is odd and the addition of all vertices not of this type is even there must be an odd number of vertices of this form.

Note: if we sub $n=4k+1$ into $\frac{n-1}{2} $ it yields $2k $ and $d=2k$ by above.

Really unhappy with this argument Any help in improving it or an alternative argument that's more coherent much appreciated.

Answer 1

Note that the total sum of the degrees of every node in any undirected graph must be even since each edge bridges two nodes.

Also note that the total number of nodes is odd. So, showing that there are an even number of nodes with degree $\neq\frac{n-1}2$ is sufficient.

This can be shown through the following argument. The maximum degree of a given node in the graph is $n-1$. So, if node $v$ has degree $d$ in the graph, it has degree $n-(d+1)$ in the complement. These degrees cannot be equal unless $d=\frac{n-1}2$. So, since the graph is self-complementary, for each node $v$ in the graph with $d\neq\frac{n-1}2$, there must exist a different node $v_2$ in the complement with degree $d$. We can pair off all of the nodes that have degree $\neq\frac{n-1}2$ as such, and since each $v_2\in$ the original graph, we have shown that all such nodes must be even.

So we are done.

Answer 2

Let $G=(V,E)$ be a self-complementary graph of order $n=4k+1$ and let $m$ be the number of vertices of degree $2k$ in $G.$ I will show that, not only is $m$ odd, but $m\equiv1\pmod4.$

Let $G'=(V,E')$ be the complement of $G.$ Let $\alpha:V\to V$ be an isomorphism between $G$ and $G',$ i.e., $\alpha$ is an anti-automorphism of $G,$ mapping edges to non-edges and non-edges to edges. For $v\in V$ let $\deg v=\deg_Gv.$

Claim 1. If $\deg v=2k$ then $\deg\alpha(v)=2k.$

Proof. $\deg v+\deg\alpha(v)=\deg_Gv+\deg_G\alpha(v)=\deg_Gv+\deg_{G'}v=n-1=4k.$

Now consider the cycle structure of $\alpha$ as a permutation of $V.$ (Note that we are using the term cycle in its group-theory sense, not its graph-theory sense!) Let $\beta$ be the permutation of $\binom V2$ induced by $\alpha,$ i.e., if $u,v$ are distinct vertices in $V,$ then $\beta(\{u,v\}=\{\alpha(u),\alpha(v)\}.$ Since $\beta$ swaps $E$ with $E',$ all cycles of $\beta$ have even length.

Claim 2. $\alpha$ has no cycles of odd length.

Proof. If $\alpha$ contained a cycle $(v_1\ v_2\ \dots\ v_s)$ of odd length $s,$ then $\beta$ would contain a cycle $(v_1v_2\ \dots\ v_sv_1)$ of odd length, which is impossible.

Claim 3. $\alpha$ has no cycles of length of the form $4t+2.$

Proof. If $\alpha$ contained a cycle $(v_1\ \dots\ v_{4t+2}),$ then $\beta$ would contain the cycle $(v_1v_{2t+2}\ v_2v_{2t+3}\ \dots\ v_{2t+1}v_{4t+2})$ of length $2t+1,$ which is impossible.

Claim 4. $\alpha$ has at most one cycle of length $1.$

Proof. If $\alpha$ had two distinct fixed points $u,v$ then the edge $uv$ would be a fixed point of $\beta,$ which is impossible.

From Claims 2–4 we see that $\alpha$ has at most one fixed point, and all other cycles have length divisible by $4.$ In fact, since $|V|=4k+1,$ $\alpha$ has exactly one fixed point. By Claim 1, the set of points of degree $2k$ is invariant under $\alpha,$ it is a union of cycles. Since the fixed point of $\alpha$ clearly has degree $2k,$ it follows that the number of vertices of degree $2k$ is congruent to $1$ modulo $4.$