Skip to main content
2 of 4
thanks removed as per https://meta.stackexchange.com/q/2950/295232

Induced matching number

Definition: A $\textit{matching}$ in a graph $G$ is a subgraph consisting of pairwise disjoint edges. If the subgraph is an induced subgraph, the matching is an $\textit{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 vertex $x$ such that $a(G \setminus x)<a(G)$ ?

user177523
  • 381
  • 2
  • 14