Graph Theory involving bipartite graphs

A bipartite graph has 16 nodes of degree 5, and some nodes of degree 8. We know that all degree-8 nodes are on the left hand side. How many degree 8 nodes can the graph have?

Hi, I am having trouble with this problem. I am not sure how to do it. Any help would be appreciated. Thank you.

1 Answer

Let's define some variables.

Let x be the number of degree-8 nodes on the left hand side.
let y be the number of degree-5 nodes on the left hand side.
let z be the number of degree-5 nodes on the right hand side.

We know the number of edges "leaving" the left hand side equals the number of edges "entering" on the right hand side.

For every degree-8 node on the left hand side, we have 8 edges leaving.
For every degree-5 node on the left hand side, we have 5 edges leaving.
For every degree-5 node on the right hand side, we have 5 edges entering.

Therefore,
$8x + 5y = 5z$

We also know that the total number of degree-5 nodes in the graph is 16.

Therefore,
$y + z = 16$

Let's start solving these equations.

$8x + 5y = 5z$
$8x + 5y + 5z = 5z + 5z$
$8x + 5(16) = 10z$
$8x = 10z - 80$
$x = \frac{5}{4}z - 10$

Let's pause for a moment. We know that x must be an integer, so z must be a multiple of 4. So z is either 0, 4, 8, 12, or 16 ($z \leq 16$ because of the equation $y+z=16$). We also know that $x \geq 0$.
So z = 8, 12, or 16. We should choose $z$ that maximizes $x$. Because $x = \frac{5}{4}z - 10$, $x$ increases with $z$, we should choose the greatest $z$, which is 16. Then $y = 0$ and $x = 10$.

ANSWER: The maximum number of degree-8 nodes in the graph is 10.

The easier way is just to look at the complete bipartite graph of 5 degree-8 nodes and 8 degree-5 nodes. Since 16 is a multiple of 8, you can just lay these complete graphs side by side and you'll end up with the required number of degree-5 nodes. Still, you'd have to go through the whole process if the number of degree-5 nodes is not a multiple of 8.