in Graph Theory recategorized ago by
98 views
2 votes
2 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$
in Graph Theory recategorized ago by
by
98 views

1 Answer

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

  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?
0
0
Answer:

Related questions