Call the "middle" vertex $B$ in a properly-connected triple $(A,B,C)$ the hub of the triple. Consider an arbitrary vertex $v$, incident to $x_i$ edges representing flights operated by the company $C_i$, for $1\leq i\leq 5$, thus with $\sum_{i=1}^5 x_i = 35$. Then the number of properly-connected triples of hub $v$ is $\sum_{i=1}^5 \binom {x_i}{2} \geq 5\binom{7}{2} = 105$, by Jensen's inequality (with equality for $x_1=x_2=x_3=x_4=x_5 = 7$), therefore the total number of properly-connected triples is at least $k=36\cdot 105 = 3780$. But it is well-known the $\binom {36}{2}$ possible pairs of vertices may be partitioned into $35$ groups, each of $18$ pairs that together contain all $36$ vertices. Assign $7$ groups to each of the $5$ companies, to get a model where the value $\boxed{k=3780}$ is actually reached, thus is the largest with the required property.

This is awful question for 6 i think. In exam, i didnt even look for a solution for 6. question. I know thats my fault but too many people did this fault. Whats the reason behind preparing this question for 6?

Probably the lack of a more appropriate question, or a misbelief on its difficulty. I agree, it's hardly a question 6.

I think you have to prove thatk=3780is the largest possible value, because what you did is only show that no matter how the situation is, there are at least 3780 properly-connected triples. But maybe i just have some misunderstndings:)

First I did show that, no matter what, there are at least $k=3780$ properly-connected triples. And then I exhibited an example with exactly $k=3780$ properly-connected triples. This shows this $k$ is the largest possible, since no larger value is reached for my example. So yes, you have some misunderstandings