**Definition:**
A *matching* in a graph $G$ is a subgraph consisting of pairwise disjoint edges. If the subgraph is an induced subgraph, the matching is an *induced matching*. The largest size of an induced matching in $G$ is called its *induced matching number* and denoted by $a(G)$.



> 
> Let $G$ be a bipartite graph.
> Is it possible to characterize the set of vertices $x$ of $G$ such that $a(G \setminus x)<a(G)$ ?
> 
> 
> 



Induced matching number
It is unlikely that a nice characterization exists because the problem of computing the size of a maximum induced matching is a well-known NP-hard problem, even for bipartite graphs (as mentioned by Peter Heinig). Therefore, unless P=NP, there is no polynomial-time algorithm that can test if a given vertex $x$ satisfies $a(G \setminus x) < a(G)$. Note that if $a(G \setminus x) < a(G)$, then $a(G \setminus x)=a(G)-1$. Therefore, if there were such an algorithm, we could simply run it and then recurse to compute $a(G)$ in polynomial time.


