Graph theory bipartite graphs

Question

What value of $\alpha$ is the graph $(K_\alpha)^c$ $\text{bipartite}$?

And, what $\alpha$ and $\beta$ make the graph $(K_{\alpha,\beta})^c$ $\text{bipartite}$?

Question: In laymans terms, what is actually being asked of me above?

Answer 1

$K_n$ usually denotes a clique of size $n$, that is, a complete graph, or in other words, a graph of $n$ vertices where there is an edge between every pair.

$K_{n,m}$ usually denotes a bipartite clique, that is, a graph formed from two sets of vertices $U$ and $V$ of sizes $n$ and $m$ respectively, such that there is an edge between each pair of vertices $(u,v)$ for $u \in U$ and $v \in V$. In other words, there are all possible edges between $U$ and $V$ and no edges inside $U$ or inside $V$.

Notation $\bullet^c$ usually denotes a complement, and in particular a graph complement in the context of graph theory. $G^c$ is a graph with same vertices as $G$ that has an edge between $v_i$ and $v_j$ if and only if $G$ does not have an edge between $v_i$ and $v_j$.

$$E(G^c) = \big\{(v_i,v_j) \mid (v_i,v_j) \notin E(G)\big\}$$

Also, if $G$ is an undirected simple graph, the complement is also treated as undirected simple graph, for example it has no loops.

Your questions asks about the values of $\alpha$ and $\beta$ which make a complement of a clique and bipartite clique a bipartite graph. For example, the complement of $K_3$ is a graph with three vertices and no edges, hence it is bipartite. On the other hand $(K_{3,2})^c$ looks like a triangle and a segment, so it is not bipartite.

I hope this helps $\ddot\smile$