# Graphs where changing any edge increases the clique or independence number

Take the cycle on $5$ vertices, $C_5$. The clique and independence number of this graph are both $2$. If we add any edge to $C_5$ we get a triangle. Meanwhile, if we remove any edge we get a triangle in the complement.

So whatever edge we change, we get either an increase (from $2$ to $3$) of the clique number, or of the independence number. Is $C_5$ the only graph with this property, or are there others?

• Interesting question. Trivially, any complete graph can only be changed by removing an edge and thus changing the independence number. (Similarly in complement, an edgeless graph) Commented Aug 16, 2017 at 15:58

Here are a few graphs with your property.

Let $\alpha(G),\ \omega(G),$ and $n(G)$ denote the independence number, the clique number, and the order of a (finite) graph $G.$

The Ramsey number $R(s,t)$ is defined by the property that $R(s,t)-1$ is the maximum possible order of a graph $G$ with $\alpha(G)\lt s$ and $\omega(G)\lt t.$ Thus, by definition (and by Ramsey's theorem which tells us that $R(s,t)$ exists), there is a graph $G_{s,t}$ (not necessarily unique) such that $\alpha(G_{s,t})=s-1,\ \omega(G_{s,t})=t-1,$ and $n(G_{s,t})=R(s,t)-1.$ In some cases such a graph $G_{s,t}$ will have your property:

Lemma. If $R(s,t)=R(s-1,t)+R(s,t-1),$ then $G_{s,t}$ has the property that removing any edge will increase the independence number, while adding any edge will increase the clique number.

Proof. The graph $G=G_{s,t}$ is regular of degree $R(s,t-1)-1.$ Adding an edge $uv$ will create a vertex $v$ of degree $R(s,t-1).$ Since $\alpha(G+uv)\le\alpha(G)\lt s,$ it follows that $v$ is in a $t$-clique of $G+uv,$ and so $\omega(G+uv)\ge t\gt\omega(G).$ Similarly, removing an edge will increase the independence number.

It's a basic lemma in Ramsey theory that the inequality $R(s,t)\le R(s-1,t)+R(s,t-1)$ always holds; it seems that the inequality is usually strict, but the equality cases give us graphs with your property.

Examples:

$R(3,3)=6=3+3=R(2,3)+R(3,2);\ G_{3,3}=C_5.$

$R(n+1,2)=n+1=R(n,2)+R(n+1,1);\ G_{n+1,2}=K_n.$

$R(2,n+1)=n+1=R(2,n)+R(1,n+1);\ G_{2,n+1}=\overline{K_n}.$

$R(3,5)=14=5+9=R(2,5)+R(3,4);$ for $G_{3,5}$ we can take $C_{13}$ and add all chords of length $5.$

$R(4,4)=18=9+9=R(3,4)+R(4,3);$ see this question or any textbook on Ramsey theory.

Nice question! No, this isn't the only nontrivial example. Take $p=13$ and construct the graph whose vertices are the residue classes mod $p$, with an edge between any two whose difference is a quadratic residue. This is well-defined (because $p\equiv 1\pmod 4$, $x-y$ is a quadratic residue if and only if $y-x$ is).

The graph is edge-transitive, since $x\mapsto a^2x+b$ is an automorphism for any $a,b\in \mathbb Z_p$ with $a\neq 0.$ It is also self-complementary (multiply by any quadratic non-residue). Thus it suffices to show that adding some edge (say $0$-$2$) increases the clique number. The clique number is $3$: the only vertices which form a triangle with $0$-$1$ are $10$ and $4$, and these four vertices don't form a clique, so $0$-$1$ isn't in a clique of size $4$ (and by transitivity neither is any other edge). But if $0$-$2$ is added then $12$-$0$-$2$-$3$ is a clique of size $4$.

It may well be that this construction works for any prime $p\equiv 1\pmod 4,$ but I can't see how to prove that.

• Forgot to point out: $C_5$ is the same construction for $p=5$. Commented Aug 22, 2017 at 13:03