spanning trees (Solved)

Importance: Medium ✭✭
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.


* indicates original appearance(s) of problem.

Solution by Ruben van der Zwaan

Where is the solution posted?


what is a support vertex?


adjacent to at least one leaf.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.