Grinberg-Introduction-Graph-Theory · Problem 5.15

Trees and arborescences

Mathematics — Graph Theory · distances-cycle-bound

Problem

Let GG be a connected multigraph. Let xx, yy, zz and ww be four vertices of GG. Assume that the two largest ones among the three numbers d(x,y)+d(z,w),d(x,z)+d(y,w)andd(x,w)+d(y,z)d(x,y) + d(z,w), \quad d(x,z) + d(y,w) \quad \text{and} \quad d(x,w) + d(y,z) are not equal. Prove that GG has a cycle of length ≤d(x,z)+d(y,w)+d(x,w)+d(y,z)\leq d(x,z) + d(y,w) + d(x,w) + d(y,z). [Hint: This is a strengthening of Exercise 5.14. Try deriving it by applying the latter exercise to a strategically chosen subgraph of GG.]

Browse the problem library