Grinberg-Introduction-Graph-Theory · Problem 2.15

Simple graphs

Mathematics — Graph Theory · matching-edge-cover

Problem

Let

G

be a simple graph with

n

vertices. Assume that each vertex of

G

has at least one neighbor. A matching of

G

shall mean a set

F

of edges of

G

such that no two edges in

F

have a vertex in common. Let

m

be the largest size of a matching of

G

. An edge cover of

G

shall mean a set

F

of edges of

G

such that each vertex of

G

is contained in at least one edge

e \in F

. Let

c

be the smallest size of an edge cover of

G

. Prove that

c + m = n