0

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.

flag

closed as off topic by Andreas Blass, Benjamin Steinberg, Steven Landsburg, Brendan McKay, Dan Petersen Apr 20 2012 at 14:15

1 Answer

2

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?

link|flag
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. – Samrat Roy Apr 20 2012 at 13:07
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}$. – Samrat Roy Apr 20 2012 at 13:18
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 – Samrat Roy Apr 20 2012 at 13:24

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