1
$\begingroup$

$G$ is a graph on $n$ vertices and $2n−2$ edges. The edges of $G$ can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G$?

  1. For every subset of $k$ vertices, the induced subgraph has at most $2k−2$ edges.
  2. The minimum cut in $G$ has at least $2$ edges.
  3. There are at least $2$ edge-disjoint paths between every pair of vertices.
  4. There are at least $2$ vertex-disjoint paths between every pair of vertices.

My attempt:

Counter for option $(4)$ is as follows: Take two copies of $K_4$(complete graph on $4$ vertices), $G_1$ and $G_2$. Let $V(G_1)=\{1,2,3,4\}$ and $V(G_2)=\{5,6,7,8\}$. Construct a new graph $G_3$ by using these two graphs $G_1$ and $G_2$ by merging at a vertex, say merge $(4,5)$. The resultant graph is two edge connected, and of minimum degree $2$ but there exist a cut vertex, the merged vertex.

Can you explain in formal/alternative way, please?

$\endgroup$
1
  • $\begingroup$ Just curious, can you give an example of where these graphs are relevant? $\endgroup$
    – blue
    May 14, 2016 at 12:47

1 Answer 1

2
$\begingroup$
  1. Is true. Take the subgraphs induced by the two spanning trees, these have $k$ vertices and are cycle-free. Any cycle-free graph with k vertices has at most $k-1$ edges.

  2. Is true. Let $v, w$ be vertices from different sets of the cut. Then by 3. there are two edge-distinct paths between $v$ and $w$. So at least one of the edges of each path needs to be cut.

  3. Is true. The two spanning trees give two distinct paths which are edge-disjoint since the spanning trees are edge-disjoint.

  4. Your counter-example goes through.

$\endgroup$
2
  • $\begingroup$ In proof for 1, why restrict to only subgraphs induced by the spanning trees? The original statement only says "every subset of $k$ vertices." The cycle free assumption does not hold then. $\endgroup$ Jan 19, 2021 at 6:38
  • $\begingroup$ This was a while ago so I may be missing something. The task states that the edges of $G$ can be partitioned into two edge disjoint spanning trees. Hence the edges of the induced subgraph are precisely those that lie in one of the spanning trees and go between two of the $k$ selected vertices. So these two subgraphs contain all relevant edges. $\endgroup$
    – blue
    Jan 19, 2021 at 15:30

You must log in to answer this question.

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