recategorized by
920 views
4 votes
4 votes

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$
recategorized by

2 Answers

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

  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 votes
1 votes
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
Answer:

Related questions