0
$\begingroup$

$\Gamma = (V,E)$ is a simple undirected graph with $|V| = n$ odd vertices. $\Gamma \cong \bar{\Gamma}$ so $\Gamma$ is isomorph with its complement graph. How can i prove that there is a $i \in V$ vertex where $\deg(i) = \frac{n-1}{2}$

I know that the graph with odd number of vertices should have at least one vertex with even degree. For example the pentagon isomorph with the pentagram, and it has got more than one vertices with $\deg = \frac{5-1}{2} = 2$

My problem is, i can't prove, that the vertex has exactly $\frac{n-1}{2}$ edges connected.

$\endgroup$
3
  • $\begingroup$ What have you done so far? Have you tried to make an example of a graph isomorphic to its complement? $\endgroup$
    – saulspatz
    Commented Apr 4, 2018 at 16:05
  • $\begingroup$ Yeah i did. For example the pentagon and the pentagram are isomorph. Or the Z shape with 4 vertices is isomorph with its complement, the N shape $\endgroup$ Commented Apr 4, 2018 at 16:07
  • $\begingroup$ You should put what you have done and where you are encountering difficulties in the body of your question. Many people who are browsing questions will not read the comments. People are much more likely to help you if you show that you've made an effort yourself. Also, the moderators are likely to close your question if you don't give more context than you have. $\endgroup$
    – saulspatz
    Commented Apr 4, 2018 at 16:11

1 Answer 1

1
$\begingroup$

Sketch:

Suppose that $G$ is isomorphic to its complement $G'$ via $\phi$. Then, for every $i\in V$, there is some $j\in V$ so that $\phi(i)=j$. Then since $\deg_G(i)=\deg_{G'}(j)$ and $\deg_G(j)+\deg_{G'}(j)=n-1$, it follows that $\deg_G(i)+\deg_G(j)=n-1$.

Consider the set $\{i_1,\dots,i_k\}$ of all vertices of $G$ with $\deg_G(i_\ell)<\frac{n-1}{2}$. Each $i_\ell$ is paired with $j_\ell$ via $\phi$, i.e., $\phi(i_\ell)=j_\ell$.

If there are no vertices of degree $\frac{n-1}{2}$, then one can show that this is a complete list of the vertices of $G$ (and the two sets are disjoint). This is a contradiction, since $G$ has a odd number of vertices.

$\endgroup$
3
  • $\begingroup$ This is not correctly stated, though the idea is right. If $\phi$ is an isomorphism, it preserves vertex degrees. Also, it is not true that a bijection from a set of odd cardinality has a fixed point. I think you mean to say that $i$ and $j$ have complementary degrees as vertices of $G$. If no vertex has degree (n-1)/2 each vertex is paired with a different vertex, which is impossible if $n$ is odd. $\endgroup$
    – saulspatz
    Commented Apr 4, 2018 at 16:27
  • $\begingroup$ @saulspatz Since $\phi$ is an isomorphism to the complement, the statement about the vertex degrees is correct (and I've clarified in the answer). Also, I've corrected the pairing argument. $\endgroup$ Commented Apr 5, 2018 at 0:46
  • 1
    $\begingroup$ It reads much better now. Thanks. $\endgroup$
    – saulspatz
    Commented Apr 5, 2018 at 0:51

You must log in to answer this question.

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