„Mycielski-konstrukció” változatai közötti eltérés

A ''k''-kromatikus <math>M_k</math> Mycielski-konstrukcióval kapott gráf csak ''k''=3-ra tartalmaz Euler-kört.

<math>M_1</math> egy pontból, <math>M_2</math> két pontból és egy élből áll, tehát nem tartalmaznak Euler-kört. <math>M_3</math> egy 5 pontból álló kör, amiben van Euler-kör. A konstrukcióból adódik, hogy ugyanannyi <math>v</math> típusú csúcs van, mint amennyi <math>u</math> típusú, tehát ''k>=''&ge;3 esetén <math>w</math>-vel együtt páratlan sok csúcs van. <math>M_{k+1}</math>-ben a <math>w</math> csúcsnak <math>|V(M_k)|</math> szomszédja van, ami ''k>=''&ge;3 esetén páratlan, így ''w'' páratlan fokú. Tehát ''k''>3-ra a Mycielski-gráf nem tartalmaz Euler-kört.