Find a maximum matching in this graph

53 Views Asked by At

I need to find a maximum matching in the graph below. I have to use the bold edges for this. I would say that adding the edges $2-6$ and $7-8$ should suffice. Is there a way how I could argue that this matching is indeed a maximum matching?

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

Once every vertex is matched, your matching is obviously maximum.