Skip to main content
added 120 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

I am not sure that I understand all conditions correctly, since the question looks too straightforward, but if yes, then there are no cycles for $n\leq 2$ and for $n>2$: I claim that $c(n)=n$.

At first, $c(n)\leq n$. Indeed, no two edges of our cycle $x_1\dots x_{c(n)}x_1$ may belong to the same clique (if $c(n)\geq n+1\geq 4$), else the cycle is not induced. 

Example of induced cycle $1\dots n$ of length $n$: all edges belong to different cliques$S_i$ contains vertices $i,i+1$ (modulo $n$, alsoof course), there are commonand $n-2$ vertices for couples of non-adjacent cliques$v_{i,j}$, $j\in \{1,\dots,n\}\setminus \{i+1,i-1\}$.

I am not sure that I understand all conditions correctly, since the question looks too straightforward, but if yes, then there are no cycles for $n\leq 2$ and for $n>2$:

At first, $c(n)\leq n$. Indeed, no two edges may belong to the same clique, else the cycle is not induced. Example of induced cycle of length $n$: all edges belong to different cliques, also, there are common vertices for couples of non-adjacent cliques.

I am not sure that I understand all conditions correctly, since the question looks too straightforward, but if yes, then there are no cycles for $n\leq 2$ and for $n>2$ I claim that $c(n)=n$.

At first, $c(n)\leq n$. Indeed, no two edges of our cycle $x_1\dots x_{c(n)}x_1$ may belong to the same clique (if $c(n)\geq n+1\geq 4$), else the cycle is not induced. 

Example of induced cycle $1\dots n$ of length $n$: $S_i$ contains vertices $i,i+1$ (modulo $n$, of course), and $n-2$ vertices $v_{i,j}$, $j\in \{1,\dots,n\}\setminus \{i+1,i-1\}$.

Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

I am not sure that I understand all conditions correctly, since the question looks too straightforward, but if yes, then there are no cycles for $n\leq 2$ and for $n>2$:

At first, $c(n)\leq n$. Indeed, no two edges may belong to the same clique, else the cycle is not induced. Example of induced cycle of length $n$: all edges belong to different cliques, also, there are common vertices for couples of non-adjacent cliques.