Bipartite question Let $a,b\in\mathbb{N}$, where $a\geq b$, and let $G_{a,b}$ be the graph where $V(G_{a,b})$ is the set of all $b$-subsets of $[a]$, and two subsets $M$, $N$ are adjacent if and only if $\lvert M\bigcap N\lvert=1$.


*

*What is the number of vertices and edges in $G_{a,b}$?

*Prove that when $a\geq 3b-3 > 0$, $G_{a,b}$ is not bipartite.


Can someone help me with this please? Thanks!
 A: $\newcommand{\order}[1]{\lvert #1\rvert}$
Here are some hints:
The size of the vertex/edge sets:
The size of the vertex set should be immediate from the definition.  For the size of the edgeset, remember that the number of edges is half the total degree of the graph; perhaps it is easier to count the degree of a specific subset than to outright try to count edges?
Suppose that you have a fixed set $N\subseteq[a]$, $\order{N}=b$. The sets $M$ such that there is an edge between $N$ and $M$ are precisely those $M$ which intersect $N$ in exactly one point. If you wanted to count these, you could do so by noting that such $M$ must consist of 1 element that is in $N$, and $b-1$ elements that are in $[a]\setminus N$. Does this suggest a counting formula?
Proving the graph is not bipartite:
Here, it suffices to show that you have a triangle - that is, three sets $M,N,P\subseteq[a]$, all of size $b$, which are all connected. In other words, we must have the size of all the intersections $M\cap N$, $M\cap P$, and $N\cap P$ being exactly 1.  Can you come up with such sets?
