Dark Mode

98 views

3 votes

Let us first put lebels on the vertices :-

**Definition of matching :- **Given a graph $G(V,E) $ , a matching M in G is a set of pairwise set of non adjacent edges , that is no two edges shares common vertices .

**Definition of maximal matching :- ** A maximal matching is a matching of a graph G, that is not a subset of any other matching .

So the maximal matching possible for the given question is :-

- $\left \{ e_{1},e_{3},e_{5} \right \}$
- $\left \{ e_{2},e_{4}\right \}$
- $\left \{ e_{1},e_{4}\right \}$
- $\left \{ e_{2},e_{5}\right \}$

Maximum matching is a matching that contain maximum number of pairwise non adjacent edges .

So the given question maximum matching is $\left \{ e_{1},e_{3},e_{5} \right \}$ of size $3$ .