2
$\begingroup$

We have $n$ people and $n$ jobs. Assume that each person is able to do $k$ jobs $0<k<n$ and each job can be done by $k$ people. Proof that each job can be done at the same time

My try

Ok, I see that I can mark vertexs on two colors - so I have 2-chromatic graph. Ok, So I can represent graph as:

$$ \text{People} \hspace{3cm} \text{Jobs} \\ \bullet \hspace{4cm} \bullet \\ \bullet \hspace{4cm} \bullet \\ \bullet \hspace{4cm} \bullet \\ \bullet \hspace{4cm} \bullet \\ \cdots \\ \bullet \hspace{4cm} \bullet \\ \bullet \hspace{4cm} \bullet \\ $$ and each person and job has $k$ edges. But there I stucked :(

$\endgroup$
  • 2
    $\begingroup$ You have made a start, identifying the problem as involving a bipartite graph, one part being $n$ people and the other part being $n$ jobs to do. The key fact is that for each person, there are $k$ jobs that they could be assigned, and for each job, there are $k$ people who could do it. I'm guessing that you have been studying graph theory and matchings. So look for a Theorem you studied that applies here. The exercise is intended to reinforce your understanding of it. $\endgroup$ – hardmath Apr 19 at 17:23
  • $\begingroup$ Generally I am studying discrete mathematics (this is one of my subjects) - but this task comes from set of books which I am additionally doing and on my lecture I didn't have nothing about colors and matchings yet $\endgroup$ – VirtualUser Apr 19 at 17:33
  • 1
    $\begingroup$ There is a theorem that says k-regular bipartite graph has a perfect matching. So we don't even need the fact that each partition (Jobs, People) have the same number of vertices. You can prove the theorem using Hall's theorem. So applying Hall's theorem, pick a subset $S$ of the Jobs partition, $k|N(S)| \geq k|S|$, if $|N(S)< |S|$, then $k|N(S)|<k|S|$ which is a contradiction. Hence by Hall's theorem, there is a matching covering all jobs. Hence this shows all jobs can be done simultaneously. $\endgroup$ – mathpadawan Apr 19 at 17:41
  • $\begingroup$ The existence of perfect matchings for regular (all vertices of equal degree) bipartite graphs was previously discussed here: Prove that a k-regular bipartite graph has a perfect matching $\endgroup$ – hardmath Apr 19 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.