I understand the concept of induced subgraph, but could not understan what induced matching is. As appears in this paper, it is defined as

A matching in a graph is an induced matching if it occurs as an induced subgraph of the graph.

However, in this paper, there is a slightly different definition:

A matching in a graph is a set of edges, no two of which meet a common vertex. An induced matching M in a graph G is a matching where no two edges of M are joined by an edge of G.

Thus, I am confused since there are no example figures.

Also, there is a term called mim-width, which is maximum induced matching width and few no none examples exist in the literature.

Could you please give some examples for me to clear things out?


Both definitions are the same. An induced matching $M$ in $G$ consists of a set of edges such that $G|_{V(M)} = M$, that is, the subgraph of $G$ induced by the vertices of $M$ is exactly $M$. This is the first definition.

Now it is always the case that $G|_{V(M)} \supseteq M$, so $M$ is an induced matching if $G|_{V(M)}$ contains no other matching, that is, $G$ contains no edge connecting vertices in two different edges of $M$. This is exactly the second definition.

I have never heard of mim-width, so it is safe to assume that it will be defined in any paper which uses it. However, it probably refers to the size (probably number of edges) of the largest induced matching in the graph.

| cite | improve this answer | |
  • $\begingroup$ is this the same with independent edge cover? $\endgroup$ – padawan Nov 10 '16 at 13:00
  • $\begingroup$ I have no idea what independent edge cover is, but I bet it is defined in any paper that uses this concept. $\endgroup$ – Yuval Filmus Nov 10 '16 at 14:30
  • $\begingroup$ Induced matching requires the edges to be isolated (i.e. no common vertices, i.e. matching.) $\endgroup$ – Eran Jan 27 '19 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.