Skip to main content
added 40 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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, but every spanning tree of $G_n$ has maximum degree at least $\frac{n}{2}$.

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 satisfies the condition for $k=2$, but every spanning tree of $G_n$ has maximum degree at least $\frac{n}{2}$.

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}$.

added 288 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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 satisfies the condition for $k=2$, but every spanning tree of $G_n$ has maximum degree at least $\frac{n}{2}$.

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.

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 satisfies the condition for $k=2$, but every spanning tree of $G_n$ has maximum degree at least $\frac{n}{2}$.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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.