0
$\begingroup$

Hello,

Thank you for taking a look at this post. I am trying to prove the statement as given in the title. I have managed to disprove it but I am yet not sure if it is correct. I would appreciate it if somebody could comment if the above statement is true or false. Thank you for your time.

$\endgroup$

1 Answer 1

3
$\begingroup$

This statement is not true. For example, let $G=K_4$ and $H=C_4$, where $G$ and $H$ are complete graph and cycle graph with four vertices, respectively. It is easy to check that, $H$ is a subgraph of $G$, but $\overline{H}$ is not a subgraph of $\overline{G}$.

It is interesting that, you think about this question:

When this statement is true?

$\endgroup$
3
  • $\begingroup$ Thank you for your reply. This statement is indeed not true. I see I wrote prove in my question, it should be disprove. I will correct it now. $\endgroup$
    – Samrat Roy
    Commented Apr 20, 2012 at 13:07
  • $\begingroup$ Okay, I have corrected my statement. But please consider $G = K_3$ and $H = K_4$. Then, $\bar{G}$ is indeed subgraph of $\bar{H}$. $\endgroup$
    – Samrat Roy
    Commented Apr 20, 2012 at 13:18
  • $\begingroup$ Actually, I have not been able to show that if the subgraph, $G$ in question is complete, then somehow this statement will also fail. I think that I would need to make the complete graph as a subgraph a exception $\endgroup$
    – Samrat Roy
    Commented Apr 20, 2012 at 13:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.