251 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?
Definition of matching :- Given a graph , 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 .

Clearly see they have asked noof maximal matchings not the maximum matching.

From the above graph ,

Assume edges are e1,e2,e3,e4,e5( consecutive edges) .

The maximal matchings possible are

{ e1,e3,e5} , { e2,e4} , {e1,e4} , {e2,e5} .

So , noof maximal matchings are 4 .

If they have asked about maximum matching size then it is  3 as {e1,e3,e5} is maximum matching possible

### 1 comment

@GNANESWARA SAI Yes. 4 Maximal Matchings and 1 maximum matching.

1
1 vote
2
1 vote
3