Max matching size in a random graph Consider the random graph $G(n,\frac{1}{n})$. I'm trying to estimate the size of the maximum matching in $G$. 
If we look at one vertex, the expected value of its degree is $\frac{n-1}{n}$ so it seems like with high prob it should be 1.
So if I can show that with high probability half of the vertices has degree $1$, then with high probability the size of maximum match in $G$ would be of size $\frac{n}{4}$, but I couldn't prove it, and I'm looking for a hint on how to show that or something similar to that claim.
 A: First, just because the expected value of a fixed vertex is $\frac{n-1}{n}$ does not mean w.h.p. its degree is 1. In fact, 
$$
\text{Pr(deg(}v\text{)=1)} = {n-1 \choose 1} \frac{1}{n} \left(1-\frac{1}{n}\right)^{n-2} \approx 1 \cdot e^{-1}.
$$
Now if $X$ is the random number of vertices with degree exactly 1, then $E[X] \approx e^{-1} n$. 
Let $Y$ be the number of isolated edges. Note that there is clearly a matching that is at least $Y$. Now
$$
E[Y] = {n \choose 2} \frac{1}{n} \left(1-\frac{1}{n}\right)^{2(n-2)} \approx \frac{n}{2e^2}.
$$
Now at that remains is to show that $Y$ is concentrated around its mean. 
A: I would like to expand on the answer of D Poole, specifically to show the concentration of $Y$.
It is actually really easy if we use the method of bounded differences:

Theorem Suppose that $X_1$, $\cdots$, $X_n \in \mathcal{X}$ are independent, and $f:\mathcal{X}^n\to \mathbb{R}$. Let $c_1,\cdots,c_n$ satisfy
  $$ \sup_{x_1,\cdots,x_n,x_i'} |f(x_1,\cdots, x_{i-1},x_i,x_{i+1},\cdots, x_n) -
 f(x_1,\cdots, x_{i-1},x'_i,x_{i+1},\cdots, x_n)|\le c_i$$
  for $i=1,\cdots, n$. Then
  $$\mathrm{P}\{f-\mathbb{E}f\ge t\}\le \exp\left( \frac{-2t^2}{\sum_{i=1}^n c_i^2}\right).$$

Here we have $n \choose 2$ random variables, namely 0-1 variables saying which edges are present in the graph. When we add/remove one edge, the number of isolated edges changes by at most two. Therefore $Y$ is exponentially concentrated around the mean.
