Question:
Let $G$ be a graph with chromatic number larger than $k$, whose vertex set is partioned into sets $X$ and $Y$. Suppose that $X$ and $Y$ have the same chromatic number $k$. Prove that there is at least $k$ edges between $X$ and $Y$.
My attempt:
Suppose $e(X,Y)\le k-1$
Since $\chi (\langle X\rangle)=\chi (\langle Y\rangle)=k$ so let $X=S_1 \cup \cdots \cup S_k$ and $Y=S'_1 \cup \cdots \cup S'_k$where $S_1, \cdots, S_k, S'_1, \cdots, S'_k$ are stables partioning $X$ and $Y$.
Define a bipartite graph $H=H(X',Y')$ with $X'=s_1, \cdots, s_k$ and $Y'=s'_1, \cdots, s'_k$ such that $s_is'_j \in E(H)$ iff no vertex in $S_i$ is adjacent to a vertex in $S'_j$ (i.e. $S_i$ and $S'_j$ are stable). Also since $e(X,Y)\le k-1$ then $d(v) \ge 1$ $\forall v \in H$.
It is enough to prove that $H$ has a perfect matching.
Suppose that $H$ doesn't have a perfect matching then according to Hall-Rado's theorem, there exist a set $S \subset X$ such that $|S|>|N(S)|$
And I am struggling to find a contradiction. Actually I was trying to prove this statement, (there exist $s_i,s_j \in S$ such that they both have a unique neighbor $s'_a$) but I am not able to do it.
Can anyone help me complete my method please? Or if not maybe just give another way to solve it?
Thanks in advance.
For $S \subset X'$, there are no edges (in $H$) between $S$ and $Y' - N(S)$. What do these missing edges in $H$ tell you about the original graph $G$, especially in the case where $|N(S)| < |S|$?