3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

No, this is false. Take $K_{n, n+2}$. Removing any vertex gives a connected graph, so in particular the graph satisfies the condition with $k=2$. However, it does not contain a spanning tree with maximum degree $2$, since $K_{n, n+2}$ does not contain a Hamiltonian path.

Here is a counterexample that works for all $k$. Let $G_n$ be the graph obtained from the graph consisting of $n$ parallel edges by subdividing each edge once. This graph is $2$-connected and in particular satisfies the condition for $k=2$. However, every spanning tree of $G_n$ has maximum degree at least $\frac{n}{2}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks! Do you see a way to modify this to get a graph with vertex connectivity $1$ as well (i.e., removing some vertex does not give a connected graph)? $\endgroup$
    – user137930
    Commented Apr 5, 2019 at 0:34
  • $\begingroup$ @user137930 Add a "tail" of length 2 to the graph? Or add a mirror of the graph and "bridge" them with one vertex? $\endgroup$
    – user44191
    Commented Apr 5, 2019 at 1:30
  • $\begingroup$ @user44191 Fair enough. $\endgroup$
    – user137930
    Commented Apr 5, 2019 at 1:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .