Grinberg-Introduction-Graph-Theory · Problem 3.3

Multigraphs

Mathematics — Graph Theory · multigraph-cycle-length-divisibility

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