Problems about undirected simple graph

[MathWei]

1. Suppose that there are seven committees with each pair of committees having a common member and each person being on two committees. How many people are there?

ans: [tex]{7 \choose 2}[/tex]
2.What is the minimum number of vertices a simple graph can have if the graph has 100 edges?

ans:15

Maybe English is not my mother language leads to I really don't understand 1st problem. Can any one explain the concept using undirected graph?

About the 2nd problem, I've already known |Edges number|[tex]\le[/tex] [tex]{n \choose 2}[/tex] for undirected simple graph n:vertices number Why not n = 6??

[Guest]

Question 1 is a little bit vague. It should really say each pair of committees has precisely one member in common (otherwise you could have more than [tex]{7 \choose 2}[/tex] people).

The easiest way to answer question 1 is to imagine you have a 7 vertex graph where each vertex is one of the committees. We know a person is in exactly 2 committees, so we can think of people as edges in this graph, the end points of the edge indicating which committees the person is in. We are told every pair of committees has one person in both, this translates to saying every pair of vertices has an edge going between them. How many people are there? This is the same as asking how many edges in a 7 vertex graph where there is an edge between every pair of vertices, which is [tex]{7 \choose 2}[/tex]. (The trick to this question is to simply realise committee=vertices, people=edges.)

Question 2 is a lot easier. As you pointed out [tex]|Edges|\le{n \choose 2}[/tex]. We know [tex]|Edges|=100[/tex] from the question and by definition [tex]{n \choose 2}=n(n-1)/2[/tex]. So we want the minimum [tex]n[/tex] such that [tex]100\le n(n-1)/2[/tex].

If we try [tex]n=6[/tex] we get [tex]n(n-1)/2 = 15[/tex] which is not greater than [tex]100[/tex]. So [tex]n>6[/tex]. We could get the answer by just guessing larger values of [tex]n[/tex] till we find the right answer or we can solve the quadratic equation [tex]100=n(n-1)/2[/tex] to get [tex]n=-13.65...[/tex] or [tex]14.65...[/tex], and therefore [tex]n\geq 14.65...[/tex] so the minimum value of [tex]n[/tex] is [tex]15[/tex].

Hope this helped,

R. Baber.