If $G$ is a graph with an even number of vertices that is isomorphic to its complement $G^c$, where $f: V\longrightarrow V$ is the isomorphism, then I want to deduce that exactly one of $v$ and $f(v)$ has degree less than $\frac{1}{2}(|V| – 1)$.
I know that $\sum_vdeg(v) = \sum_vdeg(f(v))$, but I don’t know how to use the fact that the isomorphism is to $G^c$ from here. Also, I see that $\frac{1}{2}(|V| – 1)$ represents half the edges extending from any given vertex, and so a vertex $v$ will see strictly less in either $G$ or $G^c$ and strictly more in the other, to account for all possible edges between $v$ and the rest of the vertices. However, this is for the same vertex $v$ in both cases, rather than considering $v$ in one case and $f(v)$ in the other. Can someone show me what it is I am not seeing, and how to come to the desired conclusion?
Best Answer
The part about the question that is confusing is that they are talking both about $deg(v)$ and $deg(f(v))$ relative to the graph $G$. Obviously, $deg_G(v)=deg_{G^c}(f(v))$ since it is an isomorphism, so it would follow that $deg_G(v) + deg_G(f(v))=\nu-1$ (and thus at least one of them must be less than or equal to half of that).