Matchings. Independent edge set, edge cover, independent vertex set, vertex cover, their relation with each other. Definitions of v(G), p(G), a(G) and T(G). Gallai's theorems.

Independent Edge Set / Matching (!!!)

A subset of edges of a graph is called a matching or an independent edge set if no two edges share a common endpoint. A matching is said to be maximal if we cannot add any more edges to obtain a larger matching. A matching is said to be maximum if it has the largest number of edges possible in G. There is no greater matching in the graph.

ν(G) (!!!)

ν(G) is the size (number of edges) of a maximum matching in G.

Edge Cover (!!!)

An edge cover is a set S ⊂ E(G) of edges covering all vertices of G. A vertex is said to be covered if it is the endpoint of at least one edge in S. An edge cover is said to be minimal if we cannot delete any edges to obtain a smaller cover. An edge cover is said to be minimum if it has the smallest number of edges possible in G. Note: a graph with isolated vertices does not have an edge cover.

ρ(G) (!!!)

ρ(G) is the size (number of edges) of a minimum edge cover in G.

Independent Vertex Set (!!!)

A subset of vertices of a graph is called an independent vertex set if no two vertices in the set are adjacent. Said to be maximal if we cannot add any more vertices to obtain a larger independent set. Said to be maximum if it has the largest number of vertices possible in G.

α(G) (!!!)

α(G) is the size (number of vertices) of a maximum independent vertex set in G.

Vertex Cover (!!!)

A vertex cover is a set S ⊂ V(G) of vertices covering all edges of G. An edge is said to be covered if at least one of its endpoints is in S. A vertex cover is said to be minimal if we cannot delete any vertices to obtain a smaller cover. A vertex cover is said to be minimum if it has the smallest number of vertices possible in G.

τ(G) (!!!)

τ(G) is the size (number of vertices) of a minimum vertex cover in G.

Relation Between Vertex Cover and Matching (!!!)

For any simple graph G, ν(G) ≤ τ(G). Any vertex cover must contain at least one endpoint of each edge in any matching, so the minimum vertex cover is at least as large as the maximum matching.

Relation Between Edge Cover and Independent Vertex Set (!!!)

For any simple graph G, α(G) ≤ ρ(G). Each vertex in an independent set requires a distinct edge to cover it, so the minimum edge cover is at least as large as the maximum independent vertex set.

Gallai's Theorems

For any set S ⊂ V(G), S is an independent vertex set if and only if V(G) \ S is a vertex cover. Given a simple graph G with no isolated vertices and a set S of k edges: If S is a matching, then there is an edge cover in G with at most n − k edges. If S is an edge cover, then there is a matching in G with at least n − k edges.

Gallai's Theorem (!!!)

For any simple graph G: (a) α(G) + τ(G) = n (b) If G has no isolated vertices, then ν(G) + ρ(G) = n