Introduction to Graph Theory · Problem 3.12

Multigraphs — Darij Grinberg

Mathematics — Graph Theory · short-cycle-in-dense-multigraph

Problem

Let G=(V,E,φ)G = (V, E, \varphi) be a multigraph such that ∣E∣>∣V∣|E| > |V|. Prove that GG has a cycle of length ≤2n+23\leq \dfrac{2n+2}{3}, where n=∣V∣n = |V|. [Solution: This is Exercise 8 on midterm \#3 from my Spring 2017 course (except that the simple graph was replaced by a multigraph); see the course page for solutions.]

Browse the problem library