For all of the following graphs tell whether they are bipartite and provide
a certificate for your answer.
In the following two graphs, find a minimum weight perfect matching and a proof of optimality.
Do the following graphs admit a perfect matching? (motivate) Can I color their edges in three colors? (motivate)
In the following two graphs, find a minimum weight perfect matching and convince me of the optimality of the solutions you propose.
© Dipartimento di Matematica - Università di Trento