Home » Subject » Graph Theory
Importance: Medium ✭✭
Author(s):
Subject: Graph Theory
Keywords: spanning trees
Recomm. for undergrads: yes
Posted by: akhodkar
on: July 2nd, 2010
Solved by: Ruben van der Zwaan, Maastricht University
Problem   Prove or disprove: Let $ G $ be a graph with the minimum vertex degree at least 2; that is, $ \delta(G)\geq 2 $. Then there exists a spanning tree $ T $ of $ G $ such that for every support vertex $ v $ in $ T $ if $ \deg_G(v)\geq 3 $, then $ \deg_T(v)\geq 3 $.

A computer search shows that the claim is true for every graph of order at most 8 and minimum vertex degree at least 2.

Bibliography



* indicates original appearance(s) of problem.
3 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options