# For two graphs, $H$ and $G$ let $\bar{H}$ and $\bar{G}$ be their respective compliments. Then if $H$ is a subgraph of $G$, then $\bar{H}$ is a subgraph of $\bar{G}$. [closed]

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.

-

## closed as off topic by Andreas Blass, Benjamin Steinberg, Steven Landsburg, Brendan McKay, Dan PetersenApr 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.

## 1 Answer

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?

-
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