For the preferences listed below, find a solution to the stable marriage problem that, among all possible solutions, finds the most highly preferred partner for each woman.

Men's preferences:

Adam: Wanda, Xanthippe, Yasmin, Zelda

Bob: Xanthippe, Wanda, Yasmin, Zelda

Carl: Yasmin, Wanda, Xanthippe, Zelda

Don: Zelda, Wanda, Xanthippe, YasminWomen's preferences:

Wanda: Bob, Adam, Carl, Don

Xanthippe: Carl, Adam, Bob, Don

Yasmin: Bob, Adam, Carl, Don

Zelda: Carl, Adam, Don, BobFind a partition of the polygon shown below into the minimum possible number of rectangles.

Give an example of a graph that is not bipartite but that nevertheless satisfies the equation |M| + |I| = |V| where M is a maximum matching, I is a maximum independent set, and V is the set of all vertices. Show the maximum matching and maximum independent set for your example.

Find an alternating path starting at

*t*and ending at*u*in the graph shown below.