Skip to main content
MathOverflow

Return to Question

added 146 characters in body
Source Link
user137930
user137930
  • 95
  • 3

Given is a connected graph with undirected edges such that deleting any vertex decomposes the graph into $\le k$ components, for some $k\ge 2$. Is it true that the graph has a spanning tree with degree at most $k$?

The claim is clearly true if the graph itself is a tree. I checked some articles on vertex connectivity but couldn't find anything related to this.

Edit: Tony Huynh found a counterexample. What if the graph is required to be such that removing some vertex does not give a connected graph?

Given is a connected graph with undirected edges such that deleting any vertex decomposes the graph into $\le k$ components, for some $k\ge 2$. Is it true that the graph has a spanning tree with degree at most $k$?

The claim is clearly true if the graph itself is a tree. I checked some articles on vertex connectivity but couldn't find anything related to this.

Given is a connected graph with undirected edges such that deleting any vertex decomposes the graph into $\le k$ components, for some $k\ge 2$. Is it true that the graph has a spanning tree with degree at most $k$?

The claim is clearly true if the graph itself is a tree. I checked some articles on vertex connectivity but couldn't find anything related to this.

Edit: Tony Huynh found a counterexample. What if the graph is required to be such that removing some vertex does not give a connected graph?

Source Link
user137930
user137930
  • 95
  • 3

Deleting vertex decomposes graph

Given is a connected graph with undirected edges such that deleting any vertex decomposes the graph into $\le k$ components, for some $k\ge 2$. Is it true that the graph has a spanning tree with degree at most $k$?

The claim is clearly true if the graph itself is a tree. I checked some articles on vertex connectivity but couldn't find anything related to this.