Hi,
I had hoped to have 15 minutes to go over this question yesterday, but unfortunately I only had 5… I hope in the tirgulim today I will have more time…
I would first like to mention that we don't require you to give your answer in standard form, and indeed the answer is not in standard form (notice that there is an equality, which is not allowed in standard form).
You may have to read the question a few times to understand it completely, but think of it as a game:
(Let's say that the weight of a vertex is the sum of the weights of the edges touching it.)
We are given some unweighted graph G. You give me a value T, and I try to put weights on edges so that all vertices have weights strictly less than T. If I can do it, I win, otherwise you win. The only requirement from me is that the sum of the weights is one. But you are not satisfied with winning. Your goal is to give the biggest T possible that I will lose to.
Now take the first graph. If you give me T=1/2, I will fail. But that is not the biggest T you can give. You can say T=1, and no matter what I do, I won't be able to win. That is the biggest T you can give me that you will win.
In the second graph, if you say T=1, I can win, and the biggest T you can give me is 1/2…
The question is tricky because you have to realize that it's not possible to write a program that says "the maximum T so that there always exists a vertex with weight more than T" and that the question is equivalent to "what is the minimum T such that ALL vertices have weight less than T?"
This is the reason there are no weights on the graph. Also, the relationship between the maximum and minimum will become clearer next week when we talk about duality.