I'm having trouble figuring out the problem below. I've laid out my approach and it seems combinatorics formulas might help solve this. If anyone can point to me to the right direction i would greatly appreciate it. Not looking for a direct answer, just a path I can follow.


PROVE that In any group of $n \ge 1$ people, there exists a committee with the following two properties:

(a) No $2$ members of the committee are friends and

(b) Every person not included in the committee is a friend of at least $1$ member of the committee.

$n = 10$

$c$ – Committee size

$n-c$ -> every person not included in the committee

each committee member has $c-1$ enemies

$n-c$ people have at least $1$ friend who is a member of $c$


Form a graph $G$ with vertex set $V$ by letting the people be the vertices of the graph and connecting two people by an edge iff they are friends. Let $C$ be a maximal independent set of vertices: that is, no two vertices of $C$ are joined by an edge, and if $C\subsetneqq C'\subseteq V$, then $C'$ is not independent. Now use the maximality of $C$ to show that it satisfies condition (b) as well as condition (a).

  • $\begingroup$ Brian, is there a formal proof I can do some reading on for the above steps? $\endgroup$ – Java Beans Dec 8 '12 at 22:47
  • 1
    $\begingroup$ @JavaBeans: Apart from the very small missing last step, what I gave qualifies as a formal proof at the usual level of formality. Are you worried about the existence of a maximal independent set? If $v\in V$, $\{v\}$ is trivially independent, so there is at least one independent set of vertices. $V$ is finite, so among all independent sets of vertices there is at least one with the largest possible cardinality; pick one such and call it $C$. If $v\in V\setminus C$, $C\cup\{v\}$ is bigger than $C$ and therefore is not independent, so $v$ must be joined by an edge to a vertex in $C$. $\endgroup$ – Brian M. Scott Dec 8 '12 at 22:53
  • $\begingroup$ I don't understand how v ∈ V, {v} is trivially independent since there is a possibility of that all vertices are joined by an edge. $\endgroup$ – Java Beans Dec 9 '12 at 1:04
  • $\begingroup$ @JavaBeans: There is only one vertex in the set $\{v\}$, and the graph has no loops $-$ we don’t consider anyone a friend of himself $-$ so the set is necessarily independent. $A\subseteq V$ is independent if there are no edges between members of $A$; this says nothing about edges between vertices in $A$ and vertices outside of $A$. $\endgroup$ – Brian M. Scott Dec 9 '12 at 1:12
  • $\begingroup$ ok thanks brian, so just to conclude is it safe to say By maximality of C, c0 – ck can be expressed as a finite set of vertices with edges connected to only v∈V, which proves the 2 properties $\endgroup$ – Java Beans Dec 9 '12 at 2:34

Start with a committee of one person. Condition is (a) is satisfied trivially.

Now, iteratively add members to the committee so that (a) is always true. As long as (b) is false, we can find a person not in the committee who is not a friend of anyone in the committee. That means we can add them to the committee without violating (a). Rinse and repeat.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.