Maximal Matching

\begin{figure}
  \centering
  \begin{tikzpicture}
    \node (l1) [draw, circle] {};              \node (r1) [draw, circle, right=of l1] {};
    \node (l2) [draw, circle, below=of l1] {}; \node (r2) [draw, circle, below=of r1, right=of l2] {};
    \node (l3) [draw, circle, below=of l2] {}; \node (r3) [draw, circle, below=of r2, right=of l3] {};
    \node (l4) [draw, circle, below=of l3] {}; \node (r4) [draw, circle, below=of r3, right=of l4] {};
    \node (l5) [draw, circle, below=of l4] {}; \node (r5) [draw, circle, below=of r4, right=of l5] {};

    \node [left=of l4] {A};
    \node [left=of l5] {B};
    \node [right=of r5] {C};

    \draw [color=red]
	  (l1) -- (r1)
	  (l2) -- (r2)
	  (l3) -- (r3)
	  (l4) -- (r5);
    \draw [color=black!30!white]
	  (l1) -- (r2)
	  (l2) -- (r3)
	  (l2) -- (r4)
	  (l3) -- (r4)
	  (l5) -- (r5);
  \end{tikzpicture}
  \caption{An example of a maximal matching with the red lines showing the edges
included in the matching and the grey-lines showing the edges excluded from the
matching but still visible in the base graph \( G \).

There's no combination of edges from the graph \( G \) which would result in a
matching with more vertices than this one.}
  \label{fig:max-match}
\end{figure}