Graph - proving edge correspondence There are six delegates on the world festival of youth. Between three randomly chosen delegates, there are two of them that can communicate on some language. Prove that there exists a delegate triplet where communication is possible between any pair of delegates.
We can represent delegates as vertices of a graph.
Then, between three randomly picked vertices, two of them are connected.
How can we prove that there exist a delegate triplet where communication is possible between any pair of delegates?
 A: In the following we consider that connectivity between 3 vertices is sufficient for communication between them. Just in case, we define a set of vertices $(v_i)$ to be connected iff for every $v_x,v_y; x \ne y,\in (v_i)$, it is possible to travel from $v_x to v_y$ along the edges connecting the different $(v_i)$.(This was a semi formal definition). So now suppose the six vertices are a,b,c,d,e,f. Consider the triplets a,b,c, and suppose a and b communicate. Similarly among c,d,e suppose c and communicate. And among e,f,a, e and f commnicate. Convince yourself that any othercase would lead a triple i,j,k which is connected(trivial case). So now we have the graph as
$a-b, c-d,e-f$. Where $-$ denotes an edge. Next consider the triplet b,c,e. If you conectany two,supose b,c the graph looks like:
$a-b-c-d,e-f$ clearly, there exists a connected triplet and hence proved. Try it yourself with the necessary condition being a cycle.
A: This is a variation on a very famous problem. see here.
Build a complete graph in which there are $6$ vertices representing the persons. Color an edge betweent two persons red if the two persons can communicate.
By the theorem in the video there must be a red triangle or a blue triangle. But you are told by hypothesis that there is no blue triangle. Therefore we conclude a red triangle exists.
