Suppose you are given a m x n chess board. A knight can move in an L$-$shape of two squares horizontally plus one square vertically, or two sqaures vertically plus one square horizontally. The picture on the left below shows $8$ potential moves of the knight on the c$3$ on the $5$x$5$ board. On the other hand, the knight on e$4$ has only three potential moves. A knight covers the square that it's on$,$ and it can additionally cover one of the squares that it can move to$.$ For instance, in the left picture above, the knight covers c$3,$ and we may choose it to cover one additional square, say d$1.$ In the right picture, the knight covers e$4,$ and we can choose one other square, say c$5.$

We will define a valid arrangement of knights as follows:

$$ Each square contains at most one knight.

$$ Each square is covered by at most one knight. $($While each square can potentially be covered by more than one knight, we must choose which knight will cover it$.)$

$$ Each knight must cover one additional square. Describe how to build a bipartite matching model to determine the maximum size of a valid arrangement for an m X n board. Here are some pointers to help you reach your model:

$$ Think about how to construct the network that you need. Each square of the board is a node, but how do you place the arcs?

$$ The network you construct should be bipartite.

Notice that a knight on a black

square can only move to a white square, and vice versa.