The probability that the uniform random graph will be bipartite is in fact extremely low.
It is not straightforward to compute exactly, because there is a large number of ways for it to happen, and they are all dependent events. But we can get a pretty good upper bound without too much suffering.
Consider: for each partition $(A,B)$ of the vertex set, the probability that it's a bipartition is $(\frac12)^{\binom{|A|}{2}} \cdot (\frac12)^{\binom{|B|}{2}}$. That's the probability that there are no edges between two vertices in $A$, and no edges between two vertices in $B$. Given $|A|+|B|=n$ (the total number of vertices), the quantity $\binom{|A|}{2} + \binom{|B|}{2}$ is minimized when $|A| \approx |B|$; we'll take $|A|=|B|=\frac n2$, for $2\binom{n/2}{2} = \frac14 n(n-2)$ edges. In other words, the probability that $(A,B)$ is a bipartition is always less that $2^{-\frac14 n(n-2)}$.
There are $2^{n-1}$ ways to choose the bipartition $(A,B)$, up to swapping $A$ and $B$, so we have $2^{n-1}$ different probabilities of $2^{-\frac14 n(n-2)}$. The probability that any of these events happens is at most the sum of these probabilities - less, because they're not disjoint. This gives us an upper bound of $2^{(n-1) - \frac14n(n-2)} = 2^{-\frac14(n^2-6n+4)}$.
How good is this upper bound? Well, there are two sources of error:
- Not all $2^{n-1}$ pairs $(A,B)$ have $|A|=|B|=\frac n2$. However, when $n$ is even, there are $\binom{n-1}{n/2-1}$ such pairs, which is approximately $2^{n-1} \cdot \sqrt{\frac{2}{\pi n}}$; something roughly similar happens for odd $n$. The factor of $\sqrt{\frac{2}{\pi n}}$ is insignificant compared to the exponentials we've got.
- These events are not all disjoint. However, because these probabilities are so tiny, treating them as disjoint is a good approximation. (For a lower bound on the probability, we could treat them as independent, because they're actually positively correlated, and that gives approximately the same bound.)
Anyway, with a probability of at most (and very close to) $2^{-\frac14(n^2-6n+4)}$ that the random graph is bipartite, we compute that out of the $2^{\binom n2}$ possible random graphs, at most (and very close to) $2^{\binom n2 -\frac14(n^2-6n+4)}$ or $2^{n^2/4 + n -1}$ are bipartite.
I realize now that I forgot to specify "connected", but it's also true that it's very unlikely for a random graph to be disconnected, and the same estimate still works.
That's for large $n$; for small $n$, see sequence A001832 in the OEIS.
You're right about biparte graphs having at most $2$ vertices in a clique.
Proof:
Suppose that there is a clique of at least $3$ elements, $u_i$ ($i\in[3]$) then $u_1u_2u_3u_1$would be a cycle of odd length, which can't happen in biparte graphs.
Now, as you mentioned, there is an easy bijection between a matching $M\subseteq E(G)$ and $2$-cliques. However sometimes you need $1$-cliques to cover all the vertices, namely when $G$ doesn't have a perfect matching (e.g take $V=\{1,3\}\cup\{2\}$, $E=\{(1,2), (3,2)\}$). In general you can have an arbitrary amount of $1$-cliques needed to cover the vertices in a biparte graph.
Let the size of the minimum vertex covering be $\tau(G)$, the size of the maximum matching be $a_E(G)$, the minimum number of cliques that cover all vertices be $\theta(G)$ and the independence number be $a(G)$.
König tells us that $\tau(G) = a_E(G)$ and you mentioned that $\tau(G)+a(G) = |G|$. We noticed that $\theta(G) = a_E(G) + r(G)$, where $r(G)$ is the number of $1$-cliques in the minimum clique vertex cover.
Notice that $|G| - \theta(G) = a_E(G)$ (there are $2$ nodes for every $2$-clique and $1$ node for $1$-cliques, so the latter cancels out in the subtraction and we are left with the count of $2$-cliques). This equation uncovers the result
\begin{align}
|G| - \theta(G) = a_E(G) &\iff |G|-a_E(G) = \theta(G) \\
&\iff |G|-\tau(G) = \theta(G) \\
&\iff a(G) = \theta(G)
\end{align}
Best Answer
One more hint.
In a total of $mn$ edges can be drawn in a bipartite graph with parts of size $m$ and $n$. Each of these edges we either conduct or not.
Addition. Hence we conclude that the number of labelled bipartite graphs is $2^{mn}$.