The proof of Ramsey's Theorem I try to understand the proof of Ramsey's Theorem for the two color case. There are still some ambiguities.
It says $R(r-1,s)$ and $R(r,s-1)$ exists by the inductive hypothesis. I know the principle of mathematical induction, but I still don't see it.
Furthermore it says in the proof that either $|M| \geq R(r-1,s)$ or $|N| \geq R(r,s-1)$. Why does this hold? I understand that $R(r-1,s) + R(r,s-1) -1 = |M| + |N|$.
 A: Here's something about the second question:

Suppose that $a,b,x,y$ are positive, and suppose that
  $$
a + b + 1 \leq x + y
$$
  Then either $x > a$ or $y > b$.

Proof: Suppose that we do not have $x > a$, so that $x \leq a$.  We then note that
$$
a + b + 1 - x  = (a-x) + b + 1\leq y
$$
That is, we have
$$
y \geq (a - x) + b + 1 \geq b + 1 > b
$$
So, we have $y > b$.
A: Let me try to answer the first question.
The inductive hypothesis is $R(r,s)$ exists.
We know $\forall n\in N, R(n,1)=R(1,n)=1$.
Assume $\forall r<r_0, s<s_0$, $R(r,s)$ exists. (induction hypothesis)
Then we want to show $R(r_0,s_0)$ exists.
Then we apply the "Proof for Two Colors" to show that $R(r_0,s_0)≤R(r_0−1,s_0)+R(r_0,s_0−1)$, which implies $R(r_0,s_0)$ exists.
A: 
"It says $R(r-1,s)$ and $R(r,s-1)$ exists by the inductive hypothesis. I know the principle of mathematical induction, but I still don't see it."

If
$$R(r,s) \leq R(r-1,s) + R(r,s-1)\tag 1$$
then $R(r,s)$ is bounded (proving that there is a finite Ramsey number for any integers $r,s\in \mathbb N$), provided $R(r-1,s)$ and $R(r,s-1)$ exist. This is the Greenwood and Gleason upper bound.
So we assume these two Ramsey numbers do exist, and we can indeed prove that the equality holds by picking an arbitrary vertex and partitioning the rest (see proof here).
But after proving that this equality holds (provided $R(r-1,s)$ and $R(r,s-1)$ exist), we still have to get rid of this assumption, and we do so by realizing that we can keep on applying the recursion in the inequality until we are left with Ramsey numbers of the form
$$R(t-1,2)+ R(t,1)$$
At which point we resort to the "trivial" solutions $R(q,2)=q$ and $R(q,1)=1,$ justifying the previous assumptions by induction. See here:

$R(s, t) = R(t, s)$ since the colour of each edge can be swapped. Two simple
results are $R(s, 1) = 1$ and $R(s, 2) = s.$ $R(s, 1) = 1$ is trivial since $K_1$ has no
edges and so no edges to colour, thus any colouring of $K_1$ will always contain a
blue $K_1.$ $R(s, 2) = s$ is also a simple result; if all the edges of $K_s$ are coloured
red, it will contain a red $K_s,$ however if one edge is coloured blue it will contain
a blue $K_2.$ The edges of any graph of order less that $s$ could all be coloured
red in which case the graph would contain neither a red $K_s$ or a blue $K_2.$

Note that $R(q,2)=R(2,q)$ and $R(q,1)=R(1,q).$


"Furthermore it says in the proof that either $|M| \geq R(r-1,s)$ or $|N| \geq R(r,s-1)$. Why does this hold? I understand that $R(r-1,s) + R(r,s-1) -1 = |M| + |N|$."

There are two possible cases in the number of red incident edges to a random vertex $v,$ which form the set $M:$

*

*The number of red incident edges is at least $R(r-1,s),$ i.e. $\vert M \vert \geq R(r-1,s).$ If this is the case, the number of blue incident edges to $v$ needs to necessarily be at most $R(r,s-1) -1,$ or $\vert N \vert \leq R(r,s-1)-1,$ because the overall number of vertices is $R(r-1,s)+R(r,s-1),$ one more than the number of incident edges to any vertex $v.$


*The number of red incident edges is at most $R(r-1,s) -1,$ i.e. $\vert M \vert \leq R(r-1,s)-1.$ If this is the case, the number of blue incident edges to $v$ will be at least $R(r,s-1) $ or $\vert N \vert \geq R(r,s-1).$ This is clear in itself, but can also be seen as the difference between all incident edges to $v,$ which is $R(r-1,s) + R(r,s-1) - 1,$ and the maximum number of red edges $R(r-1,s) -1.$ This difference is clearly at least $R(r,s-1).$
So either $|M| \geq R(r-1,s)$ or $|N| \geq R(r,s-1)$. And the argument is completely symmetrical if we had started with the first case being red (or blue) $|M| \geq R(r,s-1).$

The rest of the proof would proceed as follows:
If we are in case 1 above, we can consider the sub-graph generated by the vertices giving incident red edges to $v,$ which are at least $R(r-1,s),$ and see that this will either have a blue $K_s,$ which would agree with the LHS of the inequality $(1);$ or $K_{r-1}$ red. In this latter situation, all we have to remember is that the vertices we are considering are all connected to $v$ via a red edge, and hence, adding back $v$ results in $K_r$ as required in the LHS of inequality $(1).$
in the case 2 above we can instead consider the sub-graph connected to $v$ by at least $R(r,s-1)$ blue edges. Again, we'll either see a clique of $K_r$ red, fulfilling the LHS of inequality $(1);$ or a blue $K_{s-1},$ which will be immediately turned into $K_s$ if we include $v.$

This is how the induction would work in concrete examples:
For $R(3,3)=6,$ the upper bound given by inequality $(1)$ determines that
$$R(3,3) \leq R(2,3) + R(3,2) = 3 + 3 = 6.$$
For $R(3,4)=9,$
$$R(3,4) \leq R(2,4) + R(3,3) = 4 + 6 = 10.$$
For $R(3,5)=14,$
$$R(3,5) \leq R(2,5) + R(3,4) = 5 + 9 = 14.$$
