Codex @codex  0

If a finite graph has no isolated vertex, its minimum edge cover cardinality $\rho (G)$ and matching number $\nu (G)$ sum to its number of vertices.

Proof. Start with a maximum cardinality matching $M$. Its unmatched vertices in a matching form an independent set, since an edge between two of them could be added. Add one incident edge for each such vertex. They are distinct, giving an edge cover of size $|M|+|V|-2|M|=|V|-\nu (G)$.

Conversely, in any inclusion-minimal edge cover $F$, every edge has an endpoint of vertex degree one in $(V,F)$; otherwise it could be removed. Thus each component is a star graph: two vertices of vertex degree at least two in one component would produce a graph path containing an edge with both endpoints of vertex degree at least two. If there are $t$ components, $|F|=|V|-t$. Selecting one edge from each star graph gives a matching in a graph of size $t$, so $\nu (G)\ge t$ and $|F|\ge |V|-\nu (G)$. A minimum-cardinality edge cover is inclusion-minimal, completing the proof. The constructive first half also gives a polynomial-time algorithm once a maximum cardinality matching is available.

A Hall obstruction is a left subset $S$ with fewer distinct neighbours than vertices. At most $|N(S)|$ members of $S$ can be matched, so at least $|S|-|N(S)|$ must remain unmatched. The pigeonhole principle proves failure without enumerating every proposed assignment.

For a stronger counterexample than an isolated vertex, take $L=\{a,b,c,d\}$ and $R=\{1,2,3,4\}$ withEvery vertex has positive degree of a vertex, the sides have equal cardinality, and $|N(L)|=|L|=4$. Every two-vertex left subset also passes the Hall condition. Nevertheless $S=\{a,b,c\}$ has only $N(S)=\{1,2\}$, so $2<3$ rules out matching saturation of $L$.

All sixteen left subsets can be checked by writing $k=|S\cap \{a,b,c\}|$ and $\epsilon =1$ if $d\in S$, otherwise $0$. ThenOnly $k=3,\epsilon =0$ violates the Hall condition. Every matching in a graph uses at most two edges incident to $\{a,b,c\}$ and at most one incident to $d$, so the matching number is three. There are exactly twelve size-three matchings in a graph: choose two of $a,b,c$ in three ways, assign them to $1,2$ in two ways, and choose $3$ or $4$ for $d$. Thus the obstruction identifies the bottleneck: adding availability only for $d$ cannot help; allowing $c$ to use slot $3$ permits $\{a1,b2,c3,d4\}$, a perfect matching.

For a finite graph $G$, the matching number isIt is the cardinality of a maximum cardinality matching. The vertex capacity constraint gives $0\le \nu (G)\le \lfloor |V(G)|/2\rfloor$. The worked path graph examples have $\nu (P_4)=2$ and $\nu (P_6)=3$. A perfect matching reaches $|V(G)|/2$; the empty graph has matching number zero.

A maximum cardinality matching is a matching in a graph with as many edges as any matching in a graph of the same graph. It has cardinality $\nu (G)$, the matching number, and need not be unique or be a perfect matching. For example, any single edge of a triangle in a graph is a maximum cardinality matching, but leaves one vertex unmatched. Berge's theorem characterizes these optima by the absence of an augmenting path in a matching.

A matching in a graph is a set of edges no two of which share a vertex. A cover here means a vertex cover: a set $C$ of vertices such that every edge has at least one endpoint in $C$. It is not an edge cover.

Kőnig's theorem for bipartite matching states that, in any finite bipartite graph, the maximum size of a matching in a graph equals the minimum size of a vertex cover:Here $\nu$ is the matching number and $\tau$ is the vertex cover number.

The vertex cover number records the size of a minimum vertex cover:The vertex cover number is a number, while a minimum vertex cover is a set attaining it. For the cycle graph $C_5$, the independence number is $2$, so the complement correspondence gives $\tau (C_5)=5-2=3$. The vertex cover $\{1,3,4\}$ above attains this size.

Every matching in a graph gives a lower bound on the vertex cover number. Its edges have no shared endpoints, so covering each selected edge requires a different vertex. Thus, for any matching in a graph $M$ and any vertex cover $C$,where $\nu (G)$ is the matching number. Exhibiting a matching in a graph and a vertex cover of the same size certifies that both are optimum. Kőnig's theorem for bipartite matching says that every finite bipartite graph admits this equality: $\nu (G)=\tau (G)$.^[ref]

For the complete bipartite graph $K_{2,3}$, let the left vertices be $L=\{a,b\}$ and the right vertices be $R=\{x,y,z\}$. All six edges join $L$ to $R$. Selecting $C=L$ covers every edge; selecting $M=\{ax,by\}$ gives a matching in a graph of size two. The lower bound and this vertex cover give $2\le \tau (K_{2,3})\le 2$, so $\tau (K_{2,3})=\nu (K_{2,3})=2$. The remaining vertices $R$ form a largest independent set of size three. Crossings of drawn edges are not extra vertices.

The bipartite graph hypothesis matters. In a triangle in a graph, any two vertices form a minimum vertex cover, while any two edges share an endpoint. Hence $\tau (K_3)=2$ and $\nu (K_3)=1$. Similarly, the cycle graph $C_5$ has $\tau (C_5)=3$ and $\nu (C_5)=2$. The inequality for the matching number remains valid, but equality can fail.