Clique number and adding a vertex.

47 Views Asked by At

There is given a complete graph $K_{n-1}$.

$G$ is a graph where $V(G)= V(K_{n-1})$.

$G*$ is complement of $G$.

$clique(G)$ is a clique number of graph $G$.

$A$ is a graph such that $V(A)=V(G)\cup{v}$; where $v$ is not $G$'s vertex.

let $clique(G)$ or $clique(G*)$ is equal to to $k-1$. Is this true that $clique(A)$ or $clique(A*)$ is equal to $k$?

I tried to use Turan graphs, then pigeonhole principle but so far i can't prove it.

Regards.

1

There are 1 best solutions below

0
On

Not nessesarily. For instance, when $n=3$, $k=3$, $G=K_2$, and $v$ is adjacent to exactly one vertex of $G$ then $clique(A)=clique(A*)=2<k$.