MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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.

share|cite|improve this question

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

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

up vote 2 down vote accepted

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?

share|cite|improve this answer
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 '12 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 '12 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 '12 at 13:24

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