以下のような証明が素朴なよい証明だと思います。

G のマッチング M に対して、 M が最大マッチングであるための必要十分条件は M に関する増加パスが存在しないことである。

必要性は明らかである。

十分性について証明する。

G は連結である場合に証明できれば、 G が連結でない場合にも、明らかに定理は成り立つ。
そのため、 G は連結であると仮定する。

G には、 M に関する増加パスが存在しないと仮定する。
M の辺に接続されていない点をFreeな点と呼ぶことにする。

G にFreeな点が2点以上存在することはないことを背理法によって証明しよう。
a, b を G の任意のFreeな2点とする。 G は連結だから、 a, b を結ぶ単純なパスが存在する。
a = a_1, …, a_k = b をその単純なパスとする。
このとき、　a_1, …, a_i に含まれるFreeな点の数が 2 であるような i ≧ 2 が存在することは明らかである。
単純なパス a_1, …, a_i は明らかに増加パスである。
これは、 G には、 M に関する増加パスが存在しないという仮定に反する。

よって、 G にFreeな点が2点以上存在することはない

G にFreeな点が1点存在する場合には、 G の点の数は、奇数であり、明らかに M は最大マッチングである。
G にFreeな点が1点も存在しない場合には、 G の点の数は、偶数であり、明らかに M は最大マッチングである。