Home » Subject » Graph Theory

spanning trees (Solved)

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.
add new comment

Solution by Ruben van der Zwaan

On May 20th, 2011 Anonymous says:

Where is the solution posted?

reply

definition?

On July 2nd, 2010 Anonymous says:

what is a support vertex?

reply

definition

On July 3rd, 2010 leshabirukov says:

adjacent to at least one leaf.

reply

Comment viewing options

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