Bariz - Problem

Not sure if this works. Answer: $\textbf{21}$. Translate the problem to graph theory. Name such graph $H$ . Color the edges of $H$ acording to the companies with blue, red and green. Let $B$, $R$ and $G$ be the number of blue, red and green edges. Since deleting the red edges leaves a conected graph, then $B+G\geq15-1=14$. Get similar inequalities for blue and green and add them. We get $edges(H)=B+R+G\geq 21$. For the construction, number the vertices $1,2 \cdots, 15$. Conect the pairs $(i,i+1),(3+i,4+i),(6+i,7+i),(9+i,10+i),(12+i,13+i),(2+i,8+1)$ and $(5+i,11+i)$. Take $i=1$ for blue, $i=2$ for red and $i=3$ for green.