For the following question, describe a graph model and then answer the question: Must the number of people at a party who do not know an odd number of people be even?
I was thinking about the corollary, where in any graph, the number of vertices of odd degree is even. Would a directed graph (tree) be the correct graph model for this problem?
Sep 7th 2007, 11:56 AM
Is "knowning" mutal? If so you use an undirected graph.
Sep 7th 2007, 12:18 PM
Ordinarily, one would not need a directed graph to model “being acquainted with”. If A knows B then we assume that B knows A.
However, if that is not a symmetric relationship then here is a counter-example to the problem. Say A, B & C are at a party. A knows B, B knows A & C and C knows A & B. In other words A does not know C. Only one, A, does not know an odd number of people.
If it is a symmetric relationship then a simple graph will work. An edge exists between two people who do not know each other then the corollary works nicely.