Edge Covering & Matching

Edge Cover

Edge Cover $F\subseteq E$ of a graph $G=(V,E)$ is a set of edges such that every vertex of the graph is incident to at least one edge of the set.

Minimum Edge Covering

$\rho (G)=|F|$ is the size (number of edges) of minimum edge cover.

Theorem 4.10 - $\rho (G)=|V|-\nu (G)$ (for graph without isolated vertices)

Matching

a matching $M\subseteq E$ in an undirected graph is a set of edges without common vertices.

Maximum matching

זיווג מקסימום

$\nu (G)=|M|$ is the size (number of edges) of maximum matching.

Perfect matching

Perfect matching in a graph is a matching that covers every vertex of the graph. A perfect matching is also a minimum-size edge cover. If there is a perfect matching, then both the matching number and the edge cover number equal $|V|/2$.

• for cycle with even length has a perfect matching.
• graph of odd vertices does not have a perfect matching.
• complete graph of even vertices always has a perfect matching.

Maximal Matching

זיווג מקסימלי להכלה A maximal matching is a matching $M$ of a graph $G$ that is not a subset of any other matching.

Matching in Bipartite graph

• see Matching in Bipartite graph