Introduction to Graph Theory · Problem 6.2

Colorings — Darij Grinberg

Mathematics — Graph Theory · proper-2-colorings

Problem

Let GG be a connected loopless multigraph. Prove that GG has a proper 2-coloring if and only if every three vertices u,v,wu, v, w of GG satisfy 2∣d(u,v)+d(v,w)+d(w,u).2 \mid d(u,v) + d(v,w) + d(w,u).

Related theory

Browse the problem library