There are $n$ aborigines on an island. Any two of them are either friends or enemies. One day, the chieftain orders that all
citizens (including himself) make and wear a necklace with zero or more stones so that:
(i) given a pair of friends, there exists a color such that each has a stone of that color; 
(ii) given a pair of enemies,there does not exist a color such that each a stone of that color.

(a) Prove that the aborigines can carry out the chieftain’s order.
(b) What is the minimum number of colors of stones required for the
aborigines to carry out the chieftain’s order?
### Part (a)
1. **Restate the problem in graph theory terms**:
   - Consider a graph \( G \) where each vertex represents an aborigine and each edge represents a friendship.
   - We need to assign colors to the vertices such that:
     - If two vertices are connected by an edge (friends), they share at least one color.
     - If two vertices are not connected by an edge (enemies), they do not share any color.

2. **Construct the solution**:
   - Enumerate the edges of \( G \) as \(\{1, 2, \dots, m\}\), where \( m \) is the number of edges.
   - For each vertex \( v \), associate a set of colors consisting of the numbers of the edges it is incident with.

3. **Verify the conditions**:
   - If two vertices \( u \) and \( v \) are friends (i.e., there is an edge \( e \) between them), then both \( u \) and \( v \) will have the color corresponding to \( e \) in their sets.
   - If two vertices \( u \) and \( v \) are enemies (i.e., there is no edge between them), then there is no common edge incident to both \( u \) and \( v \), hence no common color in their sets.

Thus, the aborigines can carry out the chieftain’s order by using the edge numbers as colors.

### Part (b)
1. **Determine the minimum number of colors**:
   - The problem asks for the minimum number of colors such that the chieftain’s order can be carried out for any possible friendship relation.

2. **Upper bound**:
   - The maximum number of edges in a graph with \( n \) vertices is \( \frac{n(n-1)}{2} \). Therefore, \( \frac{n(n-1)}{2} \) colors would be sufficient.

3. **Optimal number of colors**:
   - Consider the chromatic number of the graph. The chromatic number of a graph \( G \) is the smallest number of colors needed to color the vertices of \( G \) such that no two adjacent vertices share the same color.
   - However, the problem is not about vertex coloring but about ensuring that friends share at least one color and enemies do not share any color.
   - For a complete graph \( K_n \), only one color is needed because all vertices are friends.
   - For a general graph, the minimum number of colors required is related to the maximum clique size in the graph. The clique number \( \omega(G) \) of a graph \( G \) is the size of the largest complete subgraph (clique) in \( G \).

4. **Conclusion**:
   - The minimum number of colors required is the clique number \( \omega(G) \) of the graph \( G \).

The final answer is \( \boxed{ \omega(G) } \) (the clique number of the graph \( G \)).