Let $A$ and $B$ be the partite sets of a bipartite graph with $22$ vertices. Given that $A$ has $12$ vertices, every vertex in $A$ has degree $3$, and every vertex in $B$ has degree $2$ or $4$, determine how many vertices have degree $4$.
I tried this:
Set $n_2$, $n_3$, $n_4$ to the # of vertices with degree $2, 3, 4$. Then $n_2 + n_3 + n_4 = 22$ and $2n_2 + 3n_3 + n_4 = 2|E|$.
But I am not sure how to proceed. I guess I need to use the fact that $G$ is bipartite. But how?
Best Answer
Indeed, you have $n_3 = 12$ because $A$ has $12$ vertices and all vertices of degree $3$ are just vertices of $A$.
Your first equation now look like $n_2 + n_4 = 10$.
But since it's a bipartite graph, every edge has one "endpoint" in $A$ and another "endpoint" in $B$. By counting the "endpoints", one gets another equation: $3\times 12 = 2n_2 + 4n_4$.
This then gives $n_2 = 2$ and $n_4 = 8$.