[Math] Let $G$ be connected graph, r-regular, show that if $G^c$ is connected then….

graph theory

can you help me, if what I wrote is ok?

Let $G$ be connected graph, $r-regular$, show that if $G^c$ (G's complement) is connected, the:
a) $G$ or $G^c$ is eulerian
b) $G$ or $G^c$ is hamiltonian

$G$ has order $n$, if $G^c$ is connected the $G^c$ is $(n-r-1)-regular$

a)

  • $G$ is eulerian if $r$ is even

  • if $r$ and $n$ are odd then $G$ is no eulerian, and $G^c$ woluld be n(odd) – r (even) – 1 regular and this operation is an odd number, so none of them is eulerian (I'm not sure about this, because it says that $G$ or $G^c$ is eulerian but in this case none of them is eulerian)

  • if $r$ is odd and $n$ is even then n(even) – r(odd) – 1 this operation is and even number, then $G^c$ is eulerian

b)

A graph is hamiltonian if all its vertex has degree $\geq n/2$ so we know that $r \leq n- 1$

  • As $G$ is r-regular then in orden to be hamiltonian $r\geq n/2$ this way all its vertex fits with the condition said above.

  • $G^c$ is $(n-r-1) – regular $ then: $n-r-1 \geq \frac {n}{2}$ which is: $\frac {n}{2} – 1 \geq r$ which indicates that $\frac{n}{2} -1 \leq r \leq \frac {n}{2}$ in order to $G^c$ hamiltonian

is this the way to show it? I'm not sure, just an idea.

Best Answer

a) Hint: can both $r$ and $n$ be odd?

b) I assume that $n\ge 3$. Assume that both $G$ and $G^c$ are not Hamiltonian. Then $r<n/2$ and $n-r-1<n/2$. If $n$ is even then we have $r\le n/2-1$ and $n-r-1\le n/2-1$. Adding these inequalities, we obtain that $n-1\le n-2$, a contradiction. So $n$ is odd. If $r<(n-1)/2$ or $(n-r-1)<(n-1)/2$ then similarly to the previous we obtain a contradiction. Thus $r=n-r-1=(n-1)/2$ and both $G$ and $G^c$ are Hamiltonian by Nash-Williams theorem.

Related Question