Share $m$ candy bars for $n$ people Assume that we have $m$ candy bars and $n$ people. Each candy bar can be divided into at most two pieces (not necessarily equal). Find the necessary and sufficient condition of $(m,n)$ such that $m$ candy bars can be distributed evenly to $n$ people.
Hint (from my teacher): We consider the graph with $n$ vertices $A_1, A_2, \dots, A_n$ and connect $A_iA_j$ iff $i$-th person and $j$-th person share a candy bar, and show that if $m<n$ then the graph has no cycles.
But I don't understand how this is related to the part of the candy bar we give to each of them. It only shows that they share a candy bar, not how the bar was shared.
All ideas are appreciated!
 A: If you are connecting 2 vertices then you are drawing a diagonal and we all know diagonal divides a polygon in equal or even parts and it has to be $m<n$ as diagonals are always less than vertices. Also if you think logically you cant evenly distribute eg $7$ candies in $8$ people.
A: Consider the degree sum formula, otherwise known as the handshake lemma, which was proven by Euler in the paper on the famous "Seven Bridges of Königsberg" problem. It states that the sum of the degrees of the vertices equals 2 times the number of edges (every edge must exit and enter a vertex).
Furthermore, you know that all people must have a share of a candy bar, i.e. the graph is connected. It should now be "easy" to prove (using i.e. induction) that while m < n, there can't possibly be a cycle, otherwise the graph wouldn't be connected.
The final statement is that the candy bars must be distributed evenly, i.e. all vertices have the same degree. Without this statement, you could have had some vertices with more degrees, some with less degrees.
Edit: on mobile. I missed your bold statement. Since each edge can only connect two vertices, you'll notice that as long as there's no cycle, there's at least two odd degree vertices, kinda the begin and ending vertices. I believe the condition is E = V, forcing one big cycle. In any case, i believe your question is answered :-) .
A: Also consider if the graph is bipartite. One part $G_1$ of $m$ people having an extra candy bar, and $G_2$ of $n-m$ people that need to receive a part.
