Skip to main content
Notice removed Draw attention by Louis D
Bounty Ended with Dániel G.'s answer chosen by Louis D
added 13 characters in body
Source Link
Louis D
  • 1.7k
  • 13
  • 27

I have a two part question:

  1. Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?
    (In fact, I will give a simple proof of this below as a corollary of Theorem 1, but what I'm interested in is a proof which does not use Theorem 1 and is perhaps analogously as simple as the proof that every connected graph $G$ on $n\geq 2$ vertices contains distinct $u,v\in V(G)$ such that $G-u$ and $G-v$ are connected.)

  2. For all $n\geq 4$ there exists a strongly connected tournament $T^*$$T^*:=T^*_n$ on $n$ vertices having only two vertices $u,v$ such that $T^*-u$ and $T^*-v$ are strongly connected. Let $V(T^*)=\{v_1, \dots, v_n\}$ and $E(T^*)=\{(v_{i+1}, v_{i}): i\in [n-1]\}\cup \{(v_i, v_j): 1\leq i\leq j-2\leq n-2\}$ (in other words $T^*$ is a transitive tournament in which we reverse the direction of the edges along the path $v_1v_2\dots v_n$). Note that for all $2\leq i\leq n-1$, $T^*-v_i$ is not strongly connected.
    Is $T^*$$T^*_n$ the unique tournament with this property? That is, if $T$ is a strongly connected tournament on $n\geq 4$ vertices having exactly two vertices $u,v$ such that $T-u$ and $T-v$ are strongly connected is $T\simeq T^*$$T\simeq T^*_n$?
    I used sage/nauty to confirm this for all $4\leq n\leq 10$. Also does $T^*$$T^*_n$ have any particular name in the literature?

Theorem 1 Every strongly connected tournament $T$ on $n\geq 3$ vertices has the property that for all $3\leq k\leq n$ and all $v\in V(T)$, there exists a cycle of length $k$ containing $v$.

For a proof of this fact see Theorem 3 on Page 7 of Moon - Topics on Tournaments).

Corollary Every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected.

Proof. Let $C$ be a cycle of length $n-1$ and let $u\in V(T)\setminus V(C)$. Now let $C'$ be a cycle of length $n-1$ which contains $u$ and let $v\in V(T)\setminus V(C')$. So $u$ and $v$ are the desired vertices.

I have a two part question:

  1. Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?
    (In fact, I will give a simple proof of this below as a corollary of Theorem 1, but what I'm interested in is a proof which does not use Theorem 1 and is perhaps analogously as simple as the proof that every connected graph $G$ on $n\geq 2$ vertices contains distinct $u,v\in V(G)$ such that $G-u$ and $G-v$ are connected.)

  2. For all $n\geq 4$ there exists a strongly connected tournament $T^*$ on $n$ vertices having only two vertices $u,v$ such that $T^*-u$ and $T^*-v$ are strongly connected. Let $V(T^*)=\{v_1, \dots, v_n\}$ and $E(T^*)=\{(v_{i+1}, v_{i}): i\in [n-1]\}\cup \{(v_i, v_j): 1\leq i\leq j-2\leq n-2\}$ (in other words $T^*$ is a transitive tournament in which we reverse the direction of the edges along the path $v_1v_2\dots v_n$). Note that for all $2\leq i\leq n-1$, $T^*-v_i$ is not strongly connected.
    Is $T^*$ the unique tournament with this property? That is, if $T$ is a strongly connected tournament on $n\geq 4$ vertices having exactly two vertices $u,v$ such that $T-u$ and $T-v$ are strongly connected is $T\simeq T^*$?
    I used sage/nauty to confirm this for all $4\leq n\leq 10$. Also does $T^*$ have any particular name in the literature?

Theorem 1 Every strongly connected tournament $T$ on $n\geq 3$ vertices has the property that for all $3\leq k\leq n$ and all $v\in V(T)$, there exists a cycle of length $k$ containing $v$.

For a proof of this fact see Theorem 3 on Page 7 of Moon - Topics on Tournaments).

Corollary Every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected.

Proof. Let $C$ be a cycle of length $n-1$ and let $u\in V(T)\setminus V(C)$. Now let $C'$ be a cycle of length $n-1$ which contains $u$ and let $v\in V(T)\setminus V(C')$. So $u$ and $v$ are the desired vertices.

I have a two part question:

  1. Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?
    (In fact, I will give a simple proof of this below as a corollary of Theorem 1, but what I'm interested in is a proof which does not use Theorem 1 and is perhaps analogously as simple as the proof that every connected graph $G$ on $n\geq 2$ vertices contains distinct $u,v\in V(G)$ such that $G-u$ and $G-v$ are connected.)

  2. For all $n\geq 4$ there exists a strongly connected tournament $T^*:=T^*_n$ on $n$ vertices having only two vertices $u,v$ such that $T^*-u$ and $T^*-v$ are strongly connected. Let $V(T^*)=\{v_1, \dots, v_n\}$ and $E(T^*)=\{(v_{i+1}, v_{i}): i\in [n-1]\}\cup \{(v_i, v_j): 1\leq i\leq j-2\leq n-2\}$ (in other words $T^*$ is a transitive tournament in which we reverse the direction of the edges along the path $v_1v_2\dots v_n$). Note that for all $2\leq i\leq n-1$, $T^*-v_i$ is not strongly connected.
    Is $T^*_n$ the unique tournament with this property? That is, if $T$ is a strongly connected tournament on $n\geq 4$ vertices having exactly two vertices $u,v$ such that $T-u$ and $T-v$ are strongly connected is $T\simeq T^*_n$?
    I used sage/nauty to confirm this for all $4\leq n\leq 10$. Also does $T^*_n$ have any particular name in the literature?

Theorem 1 Every strongly connected tournament $T$ on $n\geq 3$ vertices has the property that for all $3\leq k\leq n$ and all $v\in V(T)$, there exists a cycle of length $k$ containing $v$.

For a proof of this fact see Theorem 3 on Page 7 of Moon - Topics on Tournaments).

Corollary Every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected.

Proof. Let $C$ be a cycle of length $n-1$ and let $u\in V(T)\setminus V(C)$. Now let $C'$ be a cycle of length $n-1$ which contains $u$ and let $v\in V(T)\setminus V(C')$. So $u$ and $v$ are the desired vertices.

Notice added Draw attention by Louis D
Bounty Started worth 50 reputation by Louis D
slightly modified the title
Source Link
Louis D
  • 1.7k
  • 13
  • 27

Proving that every strongly connected tournament T on at least 4 vertices contains distinct vertices u, v such that T-u and T-v are strongly connected

I have a two part question:

  1. Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?
    (In fact, I will give a simple proof of this below as a corollary of Theorem 1, but what I'm interested in is a proof which does not use Theorem 1 and is perhaps analogously as simple as the proof that every connected graph $G$ on $n\geq 2$ vertices contains distinct $u,v\in V(G)$ such that $G-u$ and $G-v$ are connected.)

  2. For all $n\geq 4$ there exists a strongly connected tournament $T^*$ on $n$ vertices having only two vertices $u,v$ such that $T^*-u$ and $T^*-v$ are strongly connected. Let $V(T^*)=\{v_1, \dots, v_n\}$ and $E(T^*)=\{(v_{i+1}, v_{i}): i\in [n-1]\}\cup \{(v_i, v_j): 1\leq i\leq j-2\leq n-2\}$ (in other words $T^*$ is a transitive tournament in which we reverse the direction of the edges along the path $v_1v_2\dots v_n$). Note that for all $2\leq i\leq n-1$, $T^*-v_i$ is not strongly connected.
    Is $T^*$ the unique tournament with this property? That is, if $T$ is a strongly connected tournament on $n\geq 4$ vertices having exactly two vertices $u,v$ such that $T-u$ and $T-v$ are strongly connected is $T\simeq T^*$?
    I used sage/nauty to confirm this for all $4\leq n\leq 10$. Also does $T^*$ have any particular name in the literature.?

Theorem 1 Every strongly connected tournament $T$ on $n\geq 3$ vertices has the property that for all $3\leq k\leq n$ and all $v\in V(T)$, there exists a cycle of length $k$ containing $v$.

For a proof of this fact see Theorem 3 on Page 7 of Moon - Topics on Tournaments).

Corollary Every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected.

Proof. Let $C$ be a cycle of length $n-1$ and let $u\in V(T)\setminus V(C)$. Now let $C'$ be a cycle of length $n-1$ which contains $u$ and let $v\in V(T)\setminus V(C')$. So $u$ and $v$ are the desired vertices.

Proving that every strongly connected tournament T on at least 4 vertices contains distinct u, v such that T-u and T-v are strongly connected

I have a two part question:

  1. Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?
    (In fact, I will give a simple proof of this below as a corollary of Theorem 1, but what I'm interested in is a proof which does not use Theorem 1 and is perhaps analogously as simple as the proof that every connected graph $G$ on $n\geq 2$ vertices contains distinct $u,v\in V(G)$ such that $G-u$ and $G-v$ are connected.)

  2. For all $n\geq 4$ there exists a strongly connected tournament $T^*$ on $n$ vertices having only two vertices $u,v$ such that $T^*-u$ and $T^*-v$ are strongly connected. Let $V(T^*)=\{v_1, \dots, v_n\}$ and $E(T^*)=\{(v_{i+1}, v_{i}): i\in [n-1]\}\cup \{(v_i, v_j): 1\leq i\leq j-2\leq n-2\}$ (in other words $T^*$ is a transitive tournament in which we reverse the direction of the edges along the path $v_1v_2\dots v_n$). Note that for all $2\leq i\leq n-1$, $T^*-v_i$ is not strongly connected.
    Is $T^*$ the unique tournament with this property? That is, if $T$ is a strongly connected tournament on $n\geq 4$ vertices having exactly two vertices $u,v$ such that $T-u$ and $T-v$ are strongly connected is $T\simeq T^*$?
    I used sage/nauty to confirm this for all $4\leq n\leq 10$. Also does $T^*$ have any particular name in the literature.

Theorem 1 Every strongly connected tournament $T$ on $n\geq 3$ vertices has the property that for all $3\leq k\leq n$ and all $v\in V(T)$, there exists a cycle of length $k$ containing $v$.

For a proof of this fact see Theorem 3 on Page 7 of Moon - Topics on Tournaments).

Corollary Every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected.

Proof. Let $C$ be a cycle of length $n-1$ and let $u\in V(T)\setminus V(C)$. Now let $C'$ be a cycle of length $n-1$ which contains $u$ and let $v\in V(T)\setminus V(C')$. So $u$ and $v$ are the desired vertices.

Proving that every strongly connected tournament T on at least 4 vertices contains distinct vertices u, v such that T-u and T-v are strongly connected

I have a two part question:

  1. Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?
    (In fact, I will give a simple proof of this below as a corollary of Theorem 1, but what I'm interested in is a proof which does not use Theorem 1 and is perhaps analogously as simple as the proof that every connected graph $G$ on $n\geq 2$ vertices contains distinct $u,v\in V(G)$ such that $G-u$ and $G-v$ are connected.)

  2. For all $n\geq 4$ there exists a strongly connected tournament $T^*$ on $n$ vertices having only two vertices $u,v$ such that $T^*-u$ and $T^*-v$ are strongly connected. Let $V(T^*)=\{v_1, \dots, v_n\}$ and $E(T^*)=\{(v_{i+1}, v_{i}): i\in [n-1]\}\cup \{(v_i, v_j): 1\leq i\leq j-2\leq n-2\}$ (in other words $T^*$ is a transitive tournament in which we reverse the direction of the edges along the path $v_1v_2\dots v_n$). Note that for all $2\leq i\leq n-1$, $T^*-v_i$ is not strongly connected.
    Is $T^*$ the unique tournament with this property? That is, if $T$ is a strongly connected tournament on $n\geq 4$ vertices having exactly two vertices $u,v$ such that $T-u$ and $T-v$ are strongly connected is $T\simeq T^*$?
    I used sage/nauty to confirm this for all $4\leq n\leq 10$. Also does $T^*$ have any particular name in the literature?

Theorem 1 Every strongly connected tournament $T$ on $n\geq 3$ vertices has the property that for all $3\leq k\leq n$ and all $v\in V(T)$, there exists a cycle of length $k$ containing $v$.

For a proof of this fact see Theorem 3 on Page 7 of Moon - Topics on Tournaments).

Corollary Every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected.

Proof. Let $C$ be a cycle of length $n-1$ and let $u\in V(T)\setminus V(C)$. Now let $C'$ be a cycle of length $n-1$ which contains $u$ and let $v\in V(T)\setminus V(C')$. So $u$ and $v$ are the desired vertices.

Source Link
Louis D
  • 1.7k
  • 13
  • 27

Proving that every strongly connected tournament T on at least 4 vertices contains distinct u, v such that T-u and T-v are strongly connected

I have a two part question:

  1. Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?
    (In fact, I will give a simple proof of this below as a corollary of Theorem 1, but what I'm interested in is a proof which does not use Theorem 1 and is perhaps analogously as simple as the proof that every connected graph $G$ on $n\geq 2$ vertices contains distinct $u,v\in V(G)$ such that $G-u$ and $G-v$ are connected.)

  2. For all $n\geq 4$ there exists a strongly connected tournament $T^*$ on $n$ vertices having only two vertices $u,v$ such that $T^*-u$ and $T^*-v$ are strongly connected. Let $V(T^*)=\{v_1, \dots, v_n\}$ and $E(T^*)=\{(v_{i+1}, v_{i}): i\in [n-1]\}\cup \{(v_i, v_j): 1\leq i\leq j-2\leq n-2\}$ (in other words $T^*$ is a transitive tournament in which we reverse the direction of the edges along the path $v_1v_2\dots v_n$). Note that for all $2\leq i\leq n-1$, $T^*-v_i$ is not strongly connected.
    Is $T^*$ the unique tournament with this property? That is, if $T$ is a strongly connected tournament on $n\geq 4$ vertices having exactly two vertices $u,v$ such that $T-u$ and $T-v$ are strongly connected is $T\simeq T^*$?
    I used sage/nauty to confirm this for all $4\leq n\leq 10$. Also does $T^*$ have any particular name in the literature.

Theorem 1 Every strongly connected tournament $T$ on $n\geq 3$ vertices has the property that for all $3\leq k\leq n$ and all $v\in V(T)$, there exists a cycle of length $k$ containing $v$.

For a proof of this fact see Theorem 3 on Page 7 of Moon - Topics on Tournaments).

Corollary Every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected.

Proof. Let $C$ be a cycle of length $n-1$ and let $u\in V(T)\setminus V(C)$. Now let $C'$ be a cycle of length $n-1$ which contains $u$ and let $v\in V(T)\setminus V(C')$. So $u$ and $v$ are the desired vertices.