Labeled Neighbourhoods in Planar Graphs 30. 11. 2011
As a motivation, notice an interesting feature - while the complete graph K6 is not planar, one can find a planar graph G and label its vertices with labels 1,2,3,4,5,6 such that every vertex v of G has neighbours of all other labels than the label of v. Try to find this example by yourself, or look here. Of course, some (or all) labels must occur multiple times in G, and it may even be helpful if some vertex has several neighbours of the same label (instead of required one). On the other hand, one cannot achieve analogous solution with seven labels (for K7) since such a labeled planar graph would need to have all degrees at least six.
Your primary assignment is to prove (or try to) the following claim:
No finite planar graph G can have vertices labeled with labels 1,2,3,4,5,6,7 such that every vertex v of G has neighbours of all other labels than the label of v, except that if v is labeled 1 or 2, then v need not have a neighbour of label 2 or 1, respectively.
In mathematical terminology, this is to prove that there is no finite planar emulator G of the graph "K7-edge".
Secondly, you may analyze the following slightly modified situation - now the task is to look at an existence of a bipartite planar graph with vertices labeled 1,2,3,4 in one part and A,B,C,D in the other part, such that every vertex labeled with a number can see all the four letters in its neighbourhood, and vice versa. Again, this is obviously not possible since such a bipartite planar graph would need to have all degrees at least 4. Your assignment is to prove (or try to) the following (stronger) claim:
No finite bipartite planar graph G can have vertices labeled with labels 1,2,3,4 in one part and A,B,C,D in the other part such that every vertex v of G labeled with a number has neighbours of all labels A,B,C,D and every vertex v of G labeled with a letter has neighbours of all labels 1,2,3,4; except that if v is labeled 1 or A, then v need not have a neighbour of label A or 1, respectively.
In mathematical terminology, this is to prove that there is no finite planar emulator G of the graph "K4,4-edge".
We suggest interested students to read more details on this topic in Lecture 11 and in the bachelor theses of Martin Derka and of Matěj Klusáček. Since this bonus assignment is quite difficult (even we do not have satisfactory answers to all these questions yet), any reasonable and significant step forward on this topic is valuable and can earn you the points. It may even happen (though very unlikely, but it happened in 2010) that one of the above claims is wrong and such a labeled graph exists - try to find it. This is getting to real science!
So good luck...