Random matching of a square lattice Suppose you have an LxL square lattice: a graph where each vertex is connected only to its four neighbours (or three when on an edge, and 2 for corners). You randomly choose a matching by randomly choosing pairs of neighbouring (and as yet unmatched) vertices. The process stops when no such pairs exist.
This process will result in a set of unmatched vertices. What is the upper bound on the number of these?
 A: Asymptotically it's about one third of the vertices. I'll prove an exact upper bound and show that we can get close to this bound.

Let $G = (V,E)$ denote the $L \times L$ grid (I assume $L$ denotes the number of vertices per side, not the number of edges, so that we have $L^2$ vertices). Let $M \subseteq E$ be a maximal matching, that is, not a maximum cardinality matching but an inclusionwise maximal matching. Now let $U \subseteq V$ be the set of unmatched vertices for this matching. Note that we have $2 \cdot |M| + |U| = L^2$.
We extend the matching to a maximal matching in the $(L+2) \times (L+2)$ grid by adding a perfect matching lying in a circle around our original grid. Let $G' = (V',E')$ denote the graph thus obtained, and $M' \subseteq E'$ the new matching. (The inclusion $\varphi : G \hookrightarrow G'$ sends the vertex $(a,b)$ to $(a + 1,b+1)$, so that $G' \setminus \text{im}(\varphi)$ is the outer ring of $G'$.) This introduces $2\cdot (L + 1)$ additional matched edges. The point of this is that now every vertex of $U$ is surrounded by four matched vertices.
We say that an unmatched vertex $u \in U$ sees an edge $e \in M'$ belonging to the matching $M'$ if $u$ is adjacent to one of the endpoints of $e$. Since no two neighbours of $u \in U$ are adjacent (the grid has no triangles), it follows that every unmatched vertex sees exactly four elements of $M'$. This is illustrated in the figure below:

Now:


*

*Every matched edge of $M' \setminus M$ (that is, the artificial outer ring that I added) is seen by at most one unmatched vertex.

*Every matched edge of $M$ is seen by at most four unmatched vertices. The endpoints of this edge have six neighbours in total, but at most four of them can be unmatched in a maximal matching:

Now we look from all vertices of $U$ and check how many matched edges we can see. Every unmatched vertex sees exactly four matched edges, so we see $4\cdot |U|$ matched edges in total. Some of these don't belong to our original matching $M$ but to $M' \setminus M$, but those edges are seen by at most one unmatched vertex. Thus, we still see at least $4 \cdot |U| - |M' \setminus M|$ matched edges from the original matching $M$. However, some edges of $M$ are counted multiple times, at most four. This finally leads to the central estimate in my solution:
$$ |M| \ \geq \ \frac{4\cdot |U| - |M'\setminus M|}{4}. $$
Now it boils down to arithmetic. Recall that we have $|M' \setminus M| = 2\cdot (L+1)$, so we find
$$ |M| \ \geq \ \frac{4\cdot |U| - 2\cdot (L+1)}{4} \ = \ |U| - \tfrac{1}{2}(L+1). $$
Equivalently:
$$ |U| \ \leq \ |M| + \tfrac{1}{2}(L + 1) \ = \ \tfrac{1}{2}(L^2 - |U|) + \tfrac{1}{2}(L + 1). $$
This gives
$$ \tfrac{3}{2}\cdot |U| \ \leq \ \tfrac{1}{2}(L^2 + L + 1), $$
hence
$$ |U| \ \leq \ \tfrac{1}{3}(L^2 + L + 1). $$
Thus, asymptotically we cannot have much more than one third of the vertices unmatched.

A simple example shows that we can get close to this upper bound:

Now there still is a bit of uncertainty about the actual maximum number of unmatched vertices: is it $\tfrac{1}{3}L^2$ or $\tfrac{1}{3}(L^2 + L + 1)$ or something in between? I'll leave the details to you. This should certainly give you a good idea what to expect. :-)
