Thread: Graph Theorey??

FOr some reason our algebra II teacher gave us this on a quiz...its like what is this?? total brute force, but i cna seem to do it...i know a little bit of graph theory, but is there a easy way to do this?

Say that there are "p" students in the classroom. For EACH integer number "q" from [0,10], one can choose 5 studnets such that exctly "q" of them know eachother. What is the minimal possible value for "p"/

A. 9 B. 10 C. 11 D. 12 E. None of the above

anybody know how to do this with Graph Theorey? What about normally?

Originally Posted by mbluo

FOr some reason our algebra II teacher gave us this on a quiz...its like what is this?? total brute force, but i cna seem to do it...i know a little bit of graph theory, but is there a easy way to do this?

Say that there are "p" students in the classroom. For EACH integer number "q" from [0,10], one can choose 5 studnets such that exctly "q" of them know eachother. What is the minimal possible value for "p"/

A. 9 B. 10 C. 11 D. 12 E. None of the above

anybody know how to do this with Graph Theorey? What about normally?

I suppose q must go from 0 to 5, not 10 (you can't select a group of five students, ten of whom know each other). Also, the case q=1, if it means anything at all, must be the same as q=0. (Five students, one of whom knows each other? That doesn't make any sense.)

The class must contain a clique of five students who all know each other (a complete subgraph on 5 vertices, if you want to put it mathematically). Suppose it also contains four (sad) students, each of whom knows nobody else in the class. That gives a total of 9 students (choice A above). By selecting q students from the clique and 5–q sad students (q=1,2,3,4,5) you can get all the possibilities required.

Originally Posted by mbluo

FOr some reason our algebra II teacher gave us this on a quiz...its like what is this?? total brute force, but i cna seem to do it...i know a little bit of graph theory, but is there a easy way to do this?

Say that there are "p" students in the classroom. For EACH integer number "q" from [0,10], one can choose 5 studnets such that exctly "q" of them IN PAIRS know eachother. What is the minimal possible value for "p"/

A. 9 B. 10 C. 11 D. 12 E. None of the above

anybody know how to do this with Graph Theorey? What about normally?

Sorry, I meant in pairs, it is 10 students, since 5C2=10. I think this makes it harder.
thanks

Ah, I see what you mean. That does make it harder. I don't have a systematic way to tackle this, but by trial and error I found a solution with nine students.



You can get each number of pairs from 0 to 10 inclusive by selecting these sets of five vertices.
For 0 pairs, BCEHJ.
For 1 pair, BCEFJ.
For 2 pairs, BFGHJ.
For 3 pairs, ABFGJ.
For 4 pairs, AFGHJ.
For 5 pairs, AEFGJ.
For 6 pairs, ACFGJ.
For 7 pairs, ACFGH.
For 8 pairs, CDEFG.
For 9 pairs, ADEFG.
For 10 pairs, ACDFG.