98 views

Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no strict superset of $M$ is a matching. How many maximal matchings does the following graph have?

1. $1$
2. $2$
3. $3$
4. $4$
5. $5$

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 :-

1. $\left \{ e_{1},e_{3},e_{5} \right \}$
2. $\left \{ e_{2},e_{4}\right \}$
3. $\left \{ e_{1},e_{4}\right \}$
4. $\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$ .

### 1 comment

they are asking how many maximal matchings possible not the maximum elements in the maximal matching right?