Skip to main content
Post Undeleted by Fedor Petrov
added 75 characters in body
Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Yes, takeAnother attempt. Take $K_{2 n} $$K_{n+1} $ and a paththree paths $abc$$abc, ade, afg$, $a\in K_{2 n} $$a\in K_{n+1} $, $b, c\notin K_{2 n} $$b, c, d, e, f, g\notin K_{n+1} $. AllAny maximal matching contains at most one of edges $ab, ad, af$, thus at least two from three edges $bc, de, fg$. Hence any two maximal matchings are perfect ant contain thehave a common edge $bc$.

Yes, take $K_{2 n} $ and a path $abc$, $a\in K_{2 n} $, $b, c\notin K_{2 n} $. All maximal matchings are perfect ant contain the edge $bc$.

Another attempt. Take $K_{n+1} $ and three paths $abc, ade, afg$, $a\in K_{n+1} $, $b, c, d, e, f, g\notin K_{n+1} $. Any maximal matching contains at most one of edges $ab, ad, af$, thus at least two from three edges $bc, de, fg$. Hence any two maximal matchings have a common edge.

Post Deleted by Fedor Petrov
Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Yes, take $K_{2 n} $ and a path $abc$, $a\in K_{2 n} $, $b, c\notin K_{2 n} $. All maximal matchings are perfect ant contain the edge $bc$.