1. Prove that for any graph, the sum the degreesPv?Vdeg(v) is twice the number of edges |E|. (By “prove” I mean write afew sentences explaining why it is true.)
2. i) At a recent math seminar, 5 mathematicians greeted eachother by shaking hands. Is it possible for each mathematician toshake hands with exactly 3 other people? (No one can shake his orher own hand.) To answer the question, please rephrase the problemas a problem about graphs (is there a graph with 5 vertices ...),state your answer, and then explain why you believe youranswer.
ii) Write a conjecture about a more general statement. What do youthink happens if we have N mathematicians and we want each to shakethe hands of K other people?
3. A very special island is inhabited only by knights andknaves. Knights always tell the truth, and knaves always lie. Youmeet two inhabitants: Zoey and Mel. Mel says, “At least one of usis a knave,” but Zoey says nothing. Can you determine who is aknight and who is a knave?
