Matching And Graph Theory 
Prove that if $G=(A \cup B,E)$ is bipartite and $|A|=n$ and $|B|=n$, $|E|>kn$ , then $G$ contains a matching of size $k+1$

I don't ask for a solution but rather idea how to approach the problem.
Another unrelated question is : I am having troubles with graph theory , I know all the theorems and lemmas , but when it comes to questions from exams I feel hopless, do you have a tip for me on how to get better at solving questions from graph theory? Or a helpfull trick on how to approach questions from graph theory?
 A: I found a solution if had $n$ vertices : Using induction on k, and the fact that there has to be a vertex of degree at least 2k+1 we can find a vertex that was not in the previous matching , and add the edge connecting both of them to the matching (we need also need to use the fact that removing any vertex still preserves the property of having more than $(k-1)$(n-1) edges)
A: I do not have a solution but a question: If I choose a star for $G$ with $6$ vertices (i.e., one as the centre of the star and $5$ satellite vertices), then $G$ is bipartite with $|V(G)| = 2 \cdot 3$ and $|E(G)| = 5 > 1 \cdot 3 = 3$. But every star contains a matching of at most one edge and not $k+1 = 2$ in this case. Do you think you have the correct theorem?
A: Since I am a stickler for details, I have the following proposal for a solution.
Let $G = (V,E) = (A\cup  B,E)$ be a (simple) balanced bipartite graph with $|V| = 2 \cdot n$ for $n \in \mathbb N$.
If $|E| > k \cdot n$ for $0 \leq k < n$, then $G$ contains a matching of size $k+1$.
We assume $n>1$ (otherwise the claim is evident) and use induction on $k$ (for graphs of the described kind).
Denote $E(U,W) := \{u w \in E:: u \in U\setminus W \wedge w \in W\setminus U\}$ for $U,W \subseteq V$ as the set of edges between vertex sets $U$ and $W$ in $G$.
We use $d(v)$ for $v \in V$ to denote the number of edges in $G$ incident with $v$.
Finally, $N(v) = \{w \in V:: v w \in E\}$ are the neighbours of $v$ in $G$.
Case 0 ($k = 0$): Since $G$ contains at least one edge, it follows that it contains a matching of size $1 = 0 + 1$.
Case 1 ($k = 1$): Then, $G$ contains a least $3$ edges.
Suppose all edges are adjacent. Choose any edge $xy \in E$.
If there are distinct edges $e_1,e_2 \in E\setminus \{xy\}$ incident with $x$ and $y$, respectively, then they are disjoint because $G$ is bipartite, 
that is, it contains no odd cycles (if $e_1$ and $e_2$ were adjacent via another vertex $z \in V\setminus \{x,y\}$, then $x y z x$ is a triangle).
This is a contradiction to the supposition. 
So, $G$ contains at least $2$ disjoint edges, i.e., a matching of size $2 = 1 + 1$.
Case 2 ($k > 1$): We know that $G$ contains a matching $M \subseteq E$ of size $k = (k-1)+1$ by induction hypothesis because $|E|>k\cdot n > (k-1)\cdot n$.
Let $A' \subseteq A$ and $B' \subseteq B$ be the set of (by $M$) matched vertices in $G$.
We see $|A'| = k = |B'|$.
Since $k<n$, there are $n-k$ unmatched vertices left in $A'' := A\setminus A'$ and $B'' := B\setminus B'$, i.e., $|A''| = n-k = |B''|$.
If there is an edge $a'' b'' \in E$ with $a'' \in A''$ and $b'' \in B''$, then we can augment the matching $M$ to $M \cup \{a'' b''\}$ of size $k+1$.
So, assume that $E(A'',B'') = \emptyset$.
Let $a b \in M$ be an edge with $a \in A'$ and $b \in B'$. 
If we can find vertices $a' \in A''$ and $b' \in B''$ with $a b', a' b \in E$,
then we can change the matching $M$ to a matching $(M\setminus \{ab\}) \cup \{a b', a' b\}$ of size $k+1$.
So, assume this is impossible, 
i.e., $\forall ab \in M: (N(a) \subseteq B' \vee N(b) \subseteq A') \wedge d(a) + d(b) \leq n + k < 2 \cdot n$.
Case 2.1 ($\forall a b \in M: d(a) + d(b) = n + k$): Then, $\{d(a), d(b)\} = \{n,k\}$.
It follows $G[A' \cup B'] = K_{k,k}$, that is, the vertices of $A'$ and $B'$ form a complete bipartite subgraph in $G$.
Therefore, if there is a vertex $a_0 \in A'$ with $d(a_0) = n$, then $\forall a \in A': d(a) = n$ and $\forall b \in B': d(b) = k$.
By symmetry of argument this holds analogously for any $b_0 \in B'$ with $d(b_0) = n$.
Without loss of generality we assume a vertex $a_0 \in A'$ with $d(a_0) = n$.
Moreover, from $E(A'',B'') = \emptyset$ and $\forall a \in A': d(a) = n$ follows $\forall b \in B: d(b) = k$ 
and so $k \cdot n < |E| = \sum_{b \in B} d(b) = n \cdot k$ which is a contradiction.
Case 2.2 ($\exists a_1 b_1 \in M: d(a_1) + d(b_1) \leq n + k - 1$): Define $H := G - \{a_1, b_1\} = (V',E')$ with $|V'|=2 \cdot (n-1)$.
Then, $|E|-(n+k-1) \leq |E'|$ and so $(k-1)\cdot (n-1) = k \cdot (n-1+1)-(n-1+k) = k \cdot n - (n+k-1) < |E'|$.
It follows that $H$ has a matching $M' \subseteq E(H)\subsetneq E(G)$ of size $k$ by induction hypothesis. 
We augment $M'$ to $M' \cup \{a_1 b_1\}$ as a matching of $G$ of size $k+1$.
A: In our case simple induction on $n$ adn $k$ would work , you justneed to observe that if thre is a matching of size $k$ , then we must have two vertices that are matced and the sum of there degree is not more than $n+k-1$
