Show that a 3-uniform hypergraph on $n \geq 5$ points, in which each pair of points occurs in the same (positive) number of edges, is not 2-colorable.

108 Views Asked by At

Here a graph is called properly colored if all of its edges contain vertices of different colors.

I'm not sure that I understand the construction in the question correctly. It seems to me the property of the graph is equivalent to having all vertices occurring in the same number of edges. If the hyperedges are represented as triangles, then the graph is a collection of triangles and is also regular.

If so isn't the following a counter-example? Each vertex belongs to four triangles, and none of the triangles is monochromatic.

enter image description here