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

Here is a proof to a related claim that hopefully will give you some ideas.

Claim. Let $X$ be an equivalence class of the entanglement relation on $V(G)$, with $|X| \geq 2$. Then for all distinct $u,v \in X$, there exist $\chi(G)-1$ edge-disjoint paths in $G$ between $u$ and $v$.

Proof. Let $k=\chi(G)$ and $V_1, \dots, V_k$ be a partition of $V(G)$ into stable sets. By relabelling, we may assume that $X \subseteq V_1$. Observe that all vertices of $X$ must be contained in some component of $G[V_1 \cup V_2]$. Otherwise, we may recolour to obtain a $k$-colouring of $G$ where two vertices of $X$ are coloured differently. In particular, for all distinct $u,v \in X$, there is a $u$--$v$ path in $G[V_1, \cup V_2]$. Repeating the argument for $i=2, \dots, k$, gives the $k-1$ edge-disjoint $u$--$v$ paths in $G$. $\square$

Note that the claim proves something stronger and weaker than what was asked in the original question. It is weaker because the paths are edge-disjoint not vertex-disjoint. But it is stronger since it holds for all distinct pairs $u,v \in X$. Moreover, the paths constructed in the proof are almost vertex-disjoint. The only vertices they have in common are in $V_1$.

Here is a proof to a related claim that hopefully will give you some ideas.

Claim. Let $X$ be an equivalence class of the entanglement relation on $V(G)$, with $|X| \geq 2$. Then for all distinct $u,v \in X$, there exist $\chi(G)-1$ edge-disjoint paths in $G$ between $u$ and $v$.

Proof. Let $k=\chi(G)$ and $V_1, \dots, V_k$ be a partition of $V(G)$ into stable sets. By relabelling, we may assume that $X \subseteq V_1$. Observe that all vertices of $X$ must be contained in some component of $G[V_1 \cup V_2]$. Otherwise, we may recolour to obtain a $k$-colouring of $G$ where two vertices of $X$ are coloured differently. In particular, for all distinct $u,v \in X$, there is a $u$--$v$ path in $G[V_1, \cup V_2]$. Repeating the argument for $i=2, \dots, k$, gives the $k-1$ edge-disjoint $u$--$v$ paths in $G$. $\square$

Note that the claim proves something stronger and weaker than what was asked in the original question. It is weaker because the paths are edge-disjoint not vertex-disjoint. But it is stronger since it holds for all distinct pairs $u,v \in X$. Moreover, the paths constructed in the proof are almost vertex-disjoint. The only vertices they have in common are in $V_1$.

Here is a proof to a related claim that hopefully will give you some ideas.

Claim. Let $X$ be an equivalence class of the entanglement relation on $V(G)$. Then for all distinct $u,v \in X$, there exist $\chi(G)-1$ edge-disjoint paths in $G$ between $u$ and $v$.

Proof. Let $k=\chi(G)$ and $V_1, \dots, V_k$ be a partition of $V(G)$ into stable sets. By relabelling, we may assume that $X \subseteq V_1$. Observe that all vertices of $X$ must be contained in some component of $G[V_1 \cup V_2]$. Otherwise, we may recolour to obtain a $k$-colouring of $G$ where two vertices of $X$ are coloured differently. In particular, for all distinct $u,v \in X$, there is a $u$--$v$ path in $G[V_1, \cup V_2]$. Repeating the argument for $i=2, \dots, k$, gives the $k-1$ edge-disjoint $u$--$v$ paths in $G$. $\square$

Note that the claim proves something stronger and weaker than what was asked in the original question. It is weaker because the paths are edge-disjoint not vertex-disjoint. But it is stronger since it holds for all distinct pairs $u,v \in X$. Moreover, the paths constructed in the proof are almost vertex-disjoint. The only vertices they have in common are in $V_1$.

deleted 2 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Here is a proof to a related claim that hopefully will give you some ideas.

Claim. Let $X$ be an equivalence class of the entanglement relation on $V(G)$, with $|X| \geq 2$. Then for all distinct $u,v \in X$, there exist $\chi(G)-1$ edge-disjoint paths in $G$ between $u$ and $v$.

Proof. Let $k=\chi(G)$ and $V_1, \dots, V_k$ be a partition of $V(G)$ into stable sets. By relabelling, we may assume that $X \subseteq V_1$. Observe that all vertices of $X$ must be contained in some component of $G[V_1 \cup V_2]$. Otherwise, we may recolour to obtain a $k$-colouring of $G$ where two vertices of $X$ are coloured differently. In particular, for all distinct $u,v \in X$, there is a $u$--$v$ path in $G[V_1, \cup V_2]$. Repeating the argument for $i=2, \dots, k$, gives the $k-1$ edge-disjoint $u$--$v$ paths in $G$. $\square$

Note that the theoremclaim proves something stronger and weaker than what was asked in the original question. It is weaker because the paths are edge-disjoint not vertex-disjoint. But it is stronger since it holds for all distinct pairs $u,v \in X$. Moreover, the paths constructed in the proof are almost vertex-disjoint. The only vertices they have in common are in $V_1$.

Here is a proof to a related claim that hopefully will give you some ideas.

Claim. Let $X$ be an equivalence class of the entanglement relation on $V(G)$, with $|X| \geq 2$. Then for all distinct $u,v \in X$, there exist $\chi(G)-1$ edge-disjoint paths in $G$ between $u$ and $v$.

Proof. Let $k=\chi(G)$ and $V_1, \dots, V_k$ be a partition of $V(G)$ into stable sets. By relabelling, we may assume that $X \subseteq V_1$. Observe that all vertices of $X$ must be contained in some component of $G[V_1 \cup V_2]$. Otherwise, we may recolour to obtain a $k$-colouring of $G$ where two vertices of $X$ are coloured differently. In particular, for all distinct $u,v \in X$, there is a $u$--$v$ path in $G[V_1, \cup V_2]$. Repeating the argument for $i=2, \dots, k$, gives the $k-1$ edge-disjoint $u$--$v$ paths in $G$. $\square$

Note that the theorem proves something stronger and weaker than what was asked in the original question. It is weaker because the paths are edge-disjoint not vertex-disjoint. But it is stronger since it holds for all distinct pairs $u,v \in X$. Moreover, the paths constructed in the proof are almost vertex-disjoint. The only vertices they have in common are in $V_1$.

Here is a proof to a related claim that hopefully will give you some ideas.

Claim. Let $X$ be an equivalence class of the entanglement relation on $V(G)$, with $|X| \geq 2$. Then for all distinct $u,v \in X$, there exist $\chi(G)-1$ edge-disjoint paths in $G$ between $u$ and $v$.

Proof. Let $k=\chi(G)$ and $V_1, \dots, V_k$ be a partition of $V(G)$ into stable sets. By relabelling, we may assume that $X \subseteq V_1$. Observe that all vertices of $X$ must be contained in some component of $G[V_1 \cup V_2]$. Otherwise, we may recolour to obtain a $k$-colouring of $G$ where two vertices of $X$ are coloured differently. In particular, for all distinct $u,v \in X$, there is a $u$--$v$ path in $G[V_1, \cup V_2]$. Repeating the argument for $i=2, \dots, k$, gives the $k-1$ edge-disjoint $u$--$v$ paths in $G$. $\square$

Note that the claim proves something stronger and weaker than what was asked in the original question. It is weaker because the paths are edge-disjoint not vertex-disjoint. But it is stronger since it holds for all distinct pairs $u,v \in X$. Moreover, the paths constructed in the proof are almost vertex-disjoint. The only vertices they have in common are in $V_1$.

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

Here is a proof to a related claim that hopefully will give you some ideas.

Claim. Let $X$ be an equivalence class of the entanglement relation on $V(G)$, with $|X| \geq 2$. Then for all distinct $u,v \in X$, there exist $\chi(G)-1$ edge-disjoint paths in $G$ between $u$ and $v$.

Proof. Let $k=\chi(G)$ and $V_1, \dots, V_k$ be a partition of $V(G)$ into stable sets. By relabelling, we may assume that $X \subseteq V_1$. Observe that all vertices of $X$ must be contained in some component of $G[V_1 \cup V_2]$. Otherwise, we may recolour to obtain a $k$-colouring of $G$ where two vertices of $X$ are coloured differently. In particular, for all distinct $u,v \in X$, there is a $u$--$v$ path in $G[V_1, \cup V_2]$. Repeating the argument for $i=2, \dots, k$, gives the $k-1$ edge-disjoint $u$--$v$ paths in $G$. $\square$

Note that the theorem proves something stronger and weaker than what was asked in the original question. It is weaker because the paths are edge-disjoint not vertex-disjoint. But it is stronger since it holds for all distinct pairs $u,v \in X$. Moreover, the paths constructed in the proof are almost vertex-disjoint. The only vertices they have in common are in $V_1$.