Introduction to Graph Theory · Problem 3.3

Multigraphs — Darij Grinberg

Mathematics — Graph Theory · multigraph-cycle-length-not-divisible

Problem

Let

G

be a multigraph with at least one vertex. Let

d > 2

be an integer. Assume that

\deg v > 2

for each vertex

v

G

. Prove that

G

has a cycle whose length is not divisible by

d