Let G be a planar graph, with edges colored red and blue. Show that there is a vertex v such that going round the vertex in a clockwise direction we encountered no more than two change of colors.
Has anybody any idea about this question?
2
-
$\begingroup$ It is a classical lemma. But it looks like homework. Better ask it elsewhere, for example, on MSE. $\endgroup$– Fedor PetrovCommented Jun 4, 2016 at 20:49
-
2$\begingroup$ It was already asked on MSE, math.stackexchange.com/questions/541651/…, and it's exercise 1.73 in Modern Graph Theory by Bollobás. $\endgroup$– Douglas ZareCommented Jun 4, 2016 at 20:50
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This is Cauchy's Combinatorial Lemma, which is Lemma 26.8 in Pak's book.
answered Jun 4, 2016 at 20:59