Graph theory Problem 'of the court'

Question

In a court trial there are n corporations which 'the enemy of my enemy is not my enemy' meaning for every 2 enemy corporations there's not another which is hostile to both of them.

For every 2 enemy corporations the court appoints a lawyer, a lawyer can't be appointed to more than pair of enemy corporations.

I want to find the largest number of lawyer's which are needed to such a court trial.

Questions: 1:Explain how this can be described as a graph theory problem.

2:Solve this problem and explain a situation where the largest number of lawyers must be used.

So far my thoughts:It's indeed a graph theory problem where there are n vertex-corporation and the graph does not contain K3 since for any 2 vertices another one thats connected with both can't exist.The number of lawyer's is equilevent to the number of edges that connect 2 vertices since each lawyer can't be appointed (each edge) to more than 2 vertices.

The second question ask me (?) when is this equation true |E(G)|= k(N-k) out of |E(G)| <= k(N-k) with k the biggest degree of a vertex (how many other corporations are enemies of that specific corporation) and N the neighbourhood of that specific vertex.

So is my answer so far correct about question1? question 2 want me to solve this, what exaclty does that means?

Answer 1

We build a graph $G$ by letting each vertex of the graph represent the corporations, and two vertices share an edge means the two cooperations are enemy with each other.

1) The graph is triangle-free if and only if the first condition is satisfied:
Proof: Suppose the graph is triangle-free, then pick a vertex $v \in V(G)$, then all neighbours of neighbours of $v$ are not adjacent to $v$, else the graph contains triangle. Hence this says that enemies of my enemies are not my enemies. Similarly, if enemies of my enemies are not my enemies, then the neighbours of neighbours of any vertex $v \in V(G)$ can't be adjacent to $v$.

For the second question, a graph $G$ on $n$ vertices satisfies $|E(G)| \leq\lfloor \frac{n^2}{4} \rfloor$ if $G$ is triangle-free. Here is the proof by induction on number of vertices $n$ of the graph: Base case: Suppose that the graph $G$ has $1$ vertex, then the claim is true. Suppose that for all graph with $n$ vertices, the claim is true and consider a triangle-free graph $G$ with $n+1$ vertices. Remove a random edge with endvertices $v,u\in V(G)$ to get a graph $G'$. Then $E(G')\leq \lfloor \frac{(n-2)^2}{4} \rfloor$. When adding the vertex $v,u$ back, $E(G) \leq \lfloor \frac{(n-2)^2}{4} \rfloor + d(v)+d(u)-1=\lfloor \frac{(n-2)^2}{4} \rfloor + n-1 \leq \frac{n^2}{4}$. And a complete bipartite graph on $n$ vertices with size of two bipartition differ by at most one has that many edges. Hence the maximum number of lawyers is $\lfloor \frac{n^2}{4} \rfloor$.

Answer 2

You formulated it as a graph theory problem perfectly.

From the answer to your other question, you know that if the maximum number of enemies a cooperation had was $k$, then you would need at most $k(n-k)$ lawyers. This is attained when there are two groups of cooperations $A$ and $B$ with sizes $k$ and $n-k$, such that everyone in the $A$ group hates everyone in the $B$ group.

Let $a=n/2-k$. Then $$ k(n-k)=(n/2-a)(n/2+a)=(n/2)^2-a^2. $$ This quantity is obviously maximized when $a$ is as closed a possible in absolute value to $0$. When $n$ is even, we get $a=0$ when $k=n/2$. Therefore, the maximum number of lawyers is $(n/2)^2$, and this maximum is attained by setting $k=n/2$ in the previous discussion. When $n$ is odd, you cannot get $a=0$. The closes you can get is $a=1/2$, which occurs when $a=\lfloor n/2\rfloor$.