# Is it possible that both a graph and its complement have small connectivity?

Let $$G=(V,E)$$ be a simple graph with $$n$$ vertices. The isoperimetric constant of $$G$$ is defined as

$$i(G) := \min_{A \subset V,|A| \leq \frac n2} \frac{|\partial A|}{|A|}$$

where $$\partial A$$ is the set edges $$uv \in E$$, with $$v \in A$$ and $$u \in A^c$$.

Is there a graph $$G$$ such that $$i(G) + i(G^c) < \frac 12$$ where $$G^c$$ denotes the complement of $$G$$?

• Would you state the definition of $\partial A$? – Wlod AA Oct 2 '18 at 8:41
• Thank you. Seems to me interesting. I'll try to look at it more. – Wlod AA Oct 2 '18 at 10:12
• It might be more interesting to consider a different scaling (i.e. not use i(G)), because otherwise as Fedja points out the sharp lower bound is 1. But the graph that witnesses this (and anything which gets close) is not so interesting - you have to find a graph such that the minimising cut, either in $G$ or $G^c$, is very unbalanced. It's (almost) obvious that if one puts a lower bound $t$ on the size of the smaller part in cuts, then one will get a lower bound on the order of $t$. – user36212 Oct 3 '18 at 9:17

## 2 Answers

It is almost obvious. Let $$i(A)=\frac{|\partial_G A|}{|A|}$$ and $$j(B)$$ be the same ratio for a vertex set $$B$$ and the complement of $$G$$. Let $$x=|A\cap B|, y=|A\cap B^c|, z=|A^c\cap B|, t=|A^c\cap B^c|$$. The edges going between $$A\cap B$$ and $$A^c\cap B^c$$ are boundary edges for both $$A$$ and $$B$$ and so are the edges between $$A^c\cap B$$ and $$A\cap B^c$$. Thus, we have $$i(A)(x+y)+j(B)(x+z)\ge xt+yz$$ If $$i(A)+j(B)<1$$, the left hand side is strictly less than $$x+\max(y,z)$$, which is at most $$xt+yz$$ if $$t,y,z>0$$. Note that if $$t=0$$, then $$x=0$$ because of the condition $$|A|,|B|\le \frac n2$$, so if $$y,z>0$$ in this case, we still have a contradiction. Finally, if, say, $$y=0$$, then $$x>0$$ (otherwise $$A=\varnothing)$$ and $$t\ge \frac n2$$ (because $$|B|\le\frac n2$$), so the RHS is at least $$\frac n2$$ while the LHS is less than $$\max(|A|,|B|)\le \frac n2$$ and we get a contradiction again.

• Nice proof, this gives a lower bound of $1$ rather than the requested $\frac{1}{2}$. But it feels like you can prove much more, perhaps $\omega(1)$? Do we have any decent upper bound? (maybe should be a new question) – usul Oct 2 '18 at 18:51
• @usul We always have a graph with one isolated vertex and everything else joined together, in which case $i(G)=0$ and $i(G^c)=1$. – fedja Oct 2 '18 at 20:48

Since for comment is long, I write the contribution here:

Let $$A$$ and $$L$$ be the adjacency matrix and Laplacian matrix of the graph $$G$$, respectively. Also, suppose $$\mu_2$$ denotes the second smallest eigenvalue of $$L$$ and $$\lambda_2$$ be the second largest eigenvalue of $$A$$. It is proved that $$i(G)\geq \frac{\mu_2}{2}$$ (see Theorem 4.1 of "Isoperimetric numbers of graphs" by Bojan Mohar). So, we have $$i(G)+i(G^c)\geq \frac{\mu_2(G)+\mu_2(G^c)}{2}$$.

So, if we have an example for your question, we must find graph $$G$$ such that $$\mu_2(G)+\mu_2(G^c)<1$$. By some spectral graph theory, it can be seen that finding such a graph is a difficult problem. But, finding the spectrum of a graph is much easier than finding its isoperimetric number.

Also, it can be shown that this problem is related to the classification of the graphs based on their second largest eigenvalue of the adjacency matrix. Actually, if we can find a suitable graph such that: $$\lambda_2(G)+\lambda_2(G^c)\leq \delta(G)-\Delta(G)+n-2$$,

Then we find an example; where $$\delta(G)$$ and $$\Delta(G)$$ shows the minimum and maximum degree of the graph $$G$$ with $$n$$ vertices.

$$\textbf{Added later:}$$ By the relation $$\mu_2(G)+\mu_2(G^c)<1$$ and some random graph testing, it seems that such graphs are so rare. There is not any example of such graph up to $$6$$ vertices. Also, it seems that we can prove $$\mu_2(G)+\mu_2(G^c)\geq 1$$, which means there is not such an example.

• Random graphs should have strong expansion properties, so are unlikely to be a source of examples. – Ben Barber Oct 2 '18 at 13:24
• @BenBarber: Yes, you are right Ben. – Shahrooz Janbaz Oct 2 '18 at 13:33
• Thanks, for responses. It seems that the validity of $\mu_2(G) + \mu_2(G^c) \geq 1$ is not obvious. – Mahdi Oct 2 '18 at 16:56
• It may be worth to mention that the inequality $μ_2(G)+μ_2(G^c)≥1$, is a conjecture here, and is open until now (@fedja: This inequality can be interesting) – Mahdi Oct 3 '18 at 19:16
• Dear @ShahroozJanbaz here arxiv.org/pdf/1901.02047.pdf, there is a proof for your claim on $μ_2(G)+μ_2(G^c)≥1$. – Mahdi Jan 9 at 3:19