AoPS Academy
Determine all sets 
containing 
and having the property that 
is prime, for all distinct 
+1 w
such that the edges 
are all the same color, say red. Now, the triangle 
must only have green and blue, since any red edge would cause a monochromatic triangle with vertex A. However, since also cannot be a monochromatic triangle, there must be at least one green edge and one blue edge. However, the common vertex of these two edges will have a green edge and a blue edge, but it will also have a red edge to 
, contradiction, hence shown.
by pidgeonhole. For 
, this claim also tells us that each vertex must have 2 edges of some color, 2 of another, and none of the last color. For now, consider the subgraph formed on the same vertex set but with only the red edges. Each vertex must have degree 2 or 0, so it must be some union of cycles. Since monochromatic triangles are not allowed, the smallest possible is a 4-cycle, which has 4 edges. Hence, there are at least 4 red edges. Similarly, since all colors are used at least once, there are also at least 4 blue edges and at least 4 green edges, contradiction since there are only 10 edges total, hence done.
with edges colored , 
, or 
. Define 
, 
, 
as the number of color , , edges incident on vertex 
. Note that 
and 
. With the conditions in the problem, we can undercount the number of triangles in the graph as
holds if and only if each vertex has two edges each of two colors. This forces us to have at least 4 edges of each color, or 12 total, contradiction. We conclude our answer is 
, which is easy to construct. 
, which is easily constructible. The corresponding graph is with each edge colored one of three colors, say red, blue, and green. The conditions then become that no vertex can have three distinct colors emanating from it, and there are no monochromatic triangles in the graph.
, there are 
edges for each vertex. This requires at least three of them to be the same color. WLOG let that color be red. Assume that vertex is , and the edges are 
, 
, and 
. In triangle 
, none of them can be red, so they must be only blue or green. By Pigeonhole, there is a point that has a blue and a green edge emanating from it, hence this is a contradiction, since it is also connected to red., each vertex has 
edges of a certain color. Hence, we can consider the subgraph formed by the red edges. It is clear that the minimum degree of a cycle is 
, which means there are at least edges of each color, a contradiction as there are only 
edges in the graph.
, which proves the bound.
. is to make a square with its sides all one mode of transportation, and the diagonals each a different mode of transportation from the sides and other diagonal.
is impossible, and it suffices to show is impossible (since we are working with complete graphs).
contain communities that allow only bus and train.
contain communities that allow only train and airplane.
contain communities that allow only bus and airplane. and . has any three communities 
, and that 
is any community in group .
and for each must be by train. and 
for 
must be by bus.
., has any two communities 
and 
, and let and 
be communities from their respective groups.
and 
are connected by train, 
is connected by airplane, and 
and 
are connected by bus.
will produce a contradiction.
communities, concluding the proof.
, we have 3 edges from the same color coming from a vertex. Now WLOG, let them be colored in color b. Now one of the edges connecting one of the b-b pairs should be in color a for example. Now from that vertex we can only have edges with a and b. Since this vertex is in an edge connecting b-b again, this edge should be colored in a, but now there is an edge coming from a vertex already having edges from color a and b, that should be in color a or b and it is in both triangle with a-a edges and b-b edges 
we get a monochromatic triangle here - contradiction. Now for n = 5, each vertex has 2 edges of a certain color there are at least 4 edges of each color - contradiction since there are only 10 edges in the graph 
. It is only left to show that n = 4 works. The example is the 
where the graph looks like a square and the two bases and two diagonals are in color a, one of the other edges is in b and the last on in c. This works n = 4 and we are ready.
?
and 
.![\[ab+bc+ac\leqslant 27\]](http://latex.artofproblemsolving.com/c/b/5/cb5e2a1efd462abd2354f4136f5fa64408f3138c.png)
. Prove that
be the number of red edges incident to vertex 
,
and 
.![\[ \binom n3 \geq \sum_u \binom{d_{r,u}}{2} + \binom{d_{g,u}}{2} + \binom{d_{b,u}}{2}. \tag{$*$} \]](http://latex.artofproblemsolving.com/1/3/3/13353f4c4a80b36e1557667632e99b5ee22fea4d.png)
However since 
and at least one of them is 
,
is at least 
,![\[ \binom n3 \geq 2n\binom{(n-1)/2}{2} \iff \frac{n-2}{6} \geq \frac{n-3}{4}. \]](http://latex.artofproblemsolving.com/8/b/3/8b343e3bd9a9fb6a813597376f94b4c5d382fe80.png)
Hence 
.
requires for all vertices 
.
is achievable by the following coloring.![[asy]
unitsize(1cm);
real r = 0.3;
void edge(pair A, pair B, pen p) { draw(A+unit(B-A)*1.5r -- B+unit(A-B)*1.5r, p); }
pair P0 = (0, 2); pair P1 = (0, 0); pair P2 = (2, 0); pair P3 = (2, 2); draw(circle(P0, r)); label("$0$", P0); draw(circle(P1, r)); label("$1$", P1); draw(circle(P2, r)); label("$2$", P2); draw(circle(P3, r)); label("$3$", P3);
edge(P0, P1, 1+blue); edge(P1, P2, 1+blue); edge(P2, P3, 1+blue); edge(P3, P0, 1+blue); edge(P0, P2, 1+red); edge(P1, P3, 1+heavygreen);
[/asy]](http://latex.artofproblemsolving.com/8/7/9/879664380cbc13f375959664098d43130198a378.png)
where 
is by bus, 
is by train, and the other four are commute through airplane.
v
are the same mode of transportation. But then the triangle formed by the three vertexes that these edges end at (other than 
)
.
by bus and 
and 
by train. Now if 
and 
are by airplane as well. We also must have 
by airplane, so this fails. If we take