The graph in your first question has no perfect matching. Since there are only $3$ vertices in $P_1$, a matching using all of those vertices can use at most $3$ of the $7$ vertices of $P_2$ and therefore cannot use all of them.
The two definitions are indeed of two different things. A perfect matching exhausts all of the vertices, so a bipartite graph that has a perfect matching must have the same number of vertices in each part. Deo is defining a directional notion: a complete matching from one part into the other. If $P_1$ and $P_2$ are the parts of a bipartite graph, $P_1$ had $m$ vertices, and $P_2$ has $n$ vertices, then a complete matching of $P_1$ into $P_2$ has $m$ edges, and a complete matching of $P_2$ into $P_1$ has $n$ edges. Thus, the former is possible only if $m\le n$, the latter is possible only if $n\le m$, and a perfect matching (which is automatically a complete matching of $P_1$ into $P_2$ and a complete matching of $P_2$ into $P_1$) is possible only if $m=n$.
The situation here is as follows. (Excuse me for repeating your conclusions.)
In fact, in the graph $G$ there exists a complete subgraph $K_{1,36}$ simply because the degree of each vertex of the graph $G$ is $36$.
Then there exists a subgraph $K_{2,12}$ and no subgraph $K_{2,n}$ with $n>12$.
There exists a subgraph $K_{4,6}$ and no subgraphs $K_{4,n}$ with $n>6$.
There are no subgraphs $K_{m,n}$ with $m\leq n$ and $m>4$ and $K_{3,n}$ with $n>6$.
This follows from this consideration.
For each fixed vertex $v$ there exists a set $U$ of vertices $G$ such that $|U|=27$ and $v,x$ have exactly $12$ common neighbors for each $x\in U$ and no more than $4$ neighbors for each $x\notin U$.
Then all complete bipartite subgraphs containing a fixed vertex $v$ and several vertices of $U$ are easily computed.
To summarize, you have actually listed all possible complete bipartite subgraphs of $G$. Apparently, if $G$ contains a subgraph $K_{m,n}$, then $G$ also contains a subgraph $K_{r,s}$ for any $r\leq m$ and $s\leq n$.
I will add more: this is a remarkable question.
Sketch of the proof.
Since the group of permutations $S_9$ lies in the group of automorphisms of the graph $G$, that is, $S_n\leq\operatorname{Aut}(G)$, we can assume that $v=(123)(456)(789)$.
Denote by $N_G(v,x)$ the set of all common neighbors of $v$ and $x$.
It is not difficult to prove that $|N_G(v,x)| =12$ if $x$ has the form $(123)(\cdots)(\cdots)$ or $(\cdots)(456)(\cdots)$ or $(\cdots)(\cdots)(789)$.
If $x$ has the form $(1\cdot\cdot)(2\cdot\cdot)(3\cdot\cdot)$, then $|N_G(v,x)|=2$.
If $x$ has the form $(12\cdot)(3\cdot\cdot)(\cdots)$ or $(13\cdot)(2\cdot\cdot)(\cdots)$ or $(23\cdot)(1\cdot\cdot)(\cdots)$
and the last bracket is not $(456)$ or $(789)$, then $|N_G(v,x)|=4$.
It follows that if the vertices $v, x_1,\ldots,x_s$, $s\geq1$, have more than four common neighbors, then they all have a common cell. We can assume that the common cell is $(123)$.
There are $10$ vertices having cell $(123)$ including $v$. We can assume that $x_1=(123)(457)(689)$ (for the third time we use that $S_n\leq\operatorname{Aut}(G)$). Now there are $8$ possibilities for choosing $x_2$. I haven't come up with anything other than a brute force, but the brute force is very small. The result is $|N_G(v,x_1,x_2)|\leq6$.
And so on.
Best Answer
Yes, your argument is valid for $K_n$ with $n \ge 3$. For $K_1$ we can construct a graph with two $K_1$ components, which is bipartite. $K_2$ itself is already bipartite so argument becomes valid when we consider larger complete graphs. As an alternative way, you can prove the following argument by induction in order to prove your argument:
since a graph is bipartite if and only if it doesn't contain an odd cycle.