My observation is : - Say for a(any) Hamilton graph of 1000 vertices , the value of its maximum matching will be 500 .
Can somebody prove it or verify it ?
Asked
Active
Viewed 63 times
0
-
So you have found a counterexample, because if $k=1000$ then $(k+1)/2=500.5\ne500$. For a smaller counterexample, take $k=5$; then $(k+1)/2=3$ but the size of a maximum matching is $2$. I think the correct formula is $\lfloor k/2\rfloor$. – bof Apr 07 '20 at 05:43
-
Any ideas on this problem : https://math.stackexchange.com/questions/3612906/maximum-matching-in-general-graph – user768815 Apr 07 '20 at 06:42