>>12949319>Connect each pair of geometric vertices of an n-dimensional hypercube to obtain a complete graph on 2^n vertices. Colour each of the edges of this graph either red or blue. What is the smallest value of n for which every such colouring contains at least one single-coloured complete subgraph on four coplanar vertices?For example, here's a 3-cube (8 vertices, 28 edges) with a single-coloured 4 vertex coplanar subgraph i.e a square with its 4 edges and 4 diagonals. One might imagine that for large dimensions one is never FORCED to have such a singly-coloured plane, since you could just take any such subgraph and change one of the colours, but if the dimension is large enough that edge is part of many square subgraphs so changing the colour in one square could cause another square containing both red and blue to now be exclusively one colour. The question is "what is the lowest dimension for which every colouring contains a single-coloured square?"
There are only a finite number of colourings of each graph, so checking this could be done by an exhaustive search, but since each graph has 2^n vertices, and edges, each of which can be coloured 1 of 2 ways, so there are possible coloured graphs graphs, every one of which might need to be checked, this quickly becomes impossible.
