Return to Answer

Here are some observations that are slightly too long for a comment. First, note that the claim is false if we replace $5$ by $4$.

Claim. There exists a graph $G$ with $\chi(G)=4$ such that $G$ does not contain a $3$-connected subgraph.

Proof. The Moser Spindle is a well-known graph with chromatic number $4$ (since it is obtained via the Hajo's construction applied to two copies of $K_4$). Moreover, it is easy to see that no subgraph of the Moser Spindle is $3$-connected. $\square$

On the other hand, every graph with chromatic number $4$ contains a subgraph which is 'almost' $3$-connected.

Claim. Every graph $G$ with $\chi(G)=4$ contains a subgraph $A$ and $x,y \in V(A)$ such that $A+xy$ is $3$-connected.

Proof. Let $G'$ be a subgraph of $G$ such that $\chi(G')=4$ and $G'$ is minimal (under the subgraph relation) with this property. If $G'$ is $3$-connected, we are done. Otherwise, let $(A,B)$ be a $(\leq 2)$-separation of $G'$ where $A$ corresponds to a leaf vertex in the SPQR tree of $G'$. By the minimality of $G'$, $\chi(A), \chi(B) \leq 3$. Thus, $(A,B)$ is a $2$-separation and the vertices $x,y \in V(A) \cap V(B)$ must be non-adjacent in $G'$ (otherwise $G'$ is $3$-colourable). Moreover, we must have $\chi(A)=\chi(B)=3$ (otherwise $G'$ is $3$-colourable). By the definition of the SPQR tree, $A+xy$ is either a cycle or is $3$-connected. However, $A+xy$ cannot be a cycle since $\chi(A)=3$. Thus, $A+xy$ is $3$-connected, as required. $\square$

Hopefully, for graphs $G$ with $\chi(G)=5$, it is not necessary to add the edge $xy$ to obtain a $3$-connected subgraph.

Here are some observations that are slightly too long for a comment. First, note that the claim is false if we replace $5$ by $4$.

Claim. There exists a graph $G$ with $\chi(G)=4$ such that $G$ does not contain a $3$-connected subgraph.

Proof. The Moser Spindle is a well-known graph with chromatic number $4$ (since it is obtained via Hajó's construction applied to two copies of $K_4$). Moreover, it is easy to see that no subgraph of the Moser Spindle is $3$-connected. $\square$

On the other hand, every graph with chromatic number $4$ contains a subgraph which is 'almost' $3$-connected.

Claim. Every graph $G$ with $\chi(G)=4$ contains a subgraph $A$ and $x,y \in V(A)$ such that $A+xy$ is $3$-connected.

Proof. Let $G'$ be a subgraph of $G$ such that $\chi(G')=4$ and $G'$ is minimal (under the subgraph relation) with this property. If $G'$ is $3$-connected, we are done. Otherwise, let $(A,B)$ be a $(\leq 2)$-separation of $G'$ where $A$ corresponds to a leaf vertex in the SPQR tree of $G'$. By the minimality of $G'$, $\chi(A), \chi(B) \leq 3$. Thus, $(A,B)$ is a $2$-separation and the vertices $x,y \in V(A) \cap V(B)$ must be non-adjacent in $G'$ (otherwise $G'$ is $3$-colourable). Moreover, we must have $\chi(A)=\chi(B)=3$ (otherwise $G'$ is $3$-colourable). By the definition of the SPQR tree, $A+xy$ is either a cycle or is $3$-connected. However, $A+xy$ cannot be a cycle since $\chi(A)=3$. Thus, $A+xy$ is $3$-connected, as required. $\square$

Hopefully, for graphs $G$ with $\chi(G)=5$, it is not necessary to add the edge $xy$ to obtain a $3$-connected subgraph.

Here are some observations that are slightly too long for a comment. First, note that the claim is false if we replace $5$ by $4$.

Claim. There exists a graph $G$ with $\chi(G)=4$ such that $G$ does not contain a $3$-connected subgraph.

Proof. The Moser Spindle is a well-known graph with chromatic number $4$ (since it is obtained via the Hajo's construction applied to two copies of $K_4$). Moreover, it is easy to see that no subgraph of the Moser Spindle is $3$-connected. $\square$

On the other hand, every graph with chromatic number $4$ contains a subgraph which is 'almost' $3$-connected.

Claim. Every graph $G$ with $\chi(G)=4$ contains a subgraph $A$ and $x,y \in V(A)$ such that $A+xy$ is $3$-connected.

Proof. Let $G'$ be a subgraph of $G$ such that $\chi(G')=4$ and $G'$ is minimal (under the subgraph relation) with this property. If $G'$ is $3$-connected, we are done. Otherwise, let $(A,B)$ be a $(\leq 2)$-separation of $G'$ where $A$ corresponds to a leaf vertex in the SPQR tree of $G'$. By the minimality of $G'$, $\chi(A), \chi(B) \leq 3$. Thus, $(A,B)$ is a $2$-separation and the vertices $x,y \in V(A) \cap V(B)$ must be non-adjacent in $G'$ (otherwise $G'$ is $3$-colourable). Moreover, we must have $\chi(A)=\chi(B)=3$ (otherwise $G'$ is $3$-colourable). By the definition of the SPQR tree, $A+xy$ is either a cycle or is $3$-connected. However, $A+xy$ cannot be a cycle since $\chi(A)=3$. Thus, $A+xy$ is $3$-connected, as required.

Here are some observations that are slightly too long for a comment. First, note that the claim is false if we replace $5$ by $4$.

Claim. There exists a graph $G$ with $\chi(G)=4$ such that $G$ does not contain a $3$-connected subgraph.

Proof. The Moser Spindle is a well-known graph with chromatic number $4$ (since it is obtained via the Hajo's construction applied to two copies of $K_4$). Moreover, it is easy to see that no subgraph of the Moser Spindle is $3$-connected. $\square$

On the other hand, every graph with chromatic number $4$ contains a subgraph which is 'almost' $3$-connected.

Claim. Every graph $G$ with $\chi(G)=4$ contains a subgraph $A$ and $x,y \in V(A)$ such that $A+xy$ is $3$-connected.

Proof. Let $G'$ be a subgraph of $G$ such that $\chi(G')=4$ and $G'$ is minimal (under the subgraph relation) with this property. If $G'$ is $3$-connected, we are done. Otherwise, let $(A,B)$ be a $(\leq 2)$-separation of $G'$ where $A$ corresponds to a leaf vertex in the SPQR tree of $G'$. By the minimality of $G'$, $\chi(A), \chi(B) \leq 3$. Thus, $(A,B)$ is a $2$-separation and the vertices $x,y \in V(A) \cap V(B)$ must be non-adjacent in $G'$ (otherwise $G'$ is $3$-colourable). Moreover, we must have $\chi(A)=\chi(B)=3$ (otherwise $G'$ is $3$-colourable). By the definition of the SPQR tree, $A+xy$ is either a cycle or is $3$-connected. However, $A+xy$ cannot be a cycle since $\chi(A)=3$. Thus, $A+xy$ is $3$-connected, as required. $\square$

Hopefully, for graphs $G$ with $\chi(G)=5$, it is not necessary to add the edge $xy$ to obtain a $3$-connected subgraph.

Here are some observations that are slightly too long for a comment. First, note that the claim is false if we replace $5$ by $4$.

Claim. There exists a graph $G$ with $\chi(G)=4$ such that $G$ does not contain a $3$-connected subgraph.

Proof. The Moser Spindle is a well-known graph with chromatic number $4$ (since it is obtained via the Hajo's construction applied to two copies of $K_4$). Moreover, it is easy to see that no subgraph of the Moser Spindle is $3$-connected.

Claim. Every graph $G$ with $\chi(G)=5$ contains a subgraph $A$ and $x,y \in V(A)$ such that $A+xy$ is $3$-connected.

Proof. Let $G'$ be a subgraph of $G$ such that $\chi(G')=5$ and $G'$ is minimal (under the subgraph relation) with this property. If $G'$ is $3$-connected, we are done. Otherwise, let $(A,B)$ be a $(\leq 2)$-separation of $G'$ where $A$ corresponds to a leaf vertex in the SPQR tree of $G'$. By the minimality of $G'$, $\chi(A), \chi(B) \leq 4$. Thus, $(A,B)$ is a $2$-separation and the vertices $x,y \in V(A) \cap V(B)$ must be non-adjacent in $G'$ (otherwise $G'$ is $4$-colourable). Moreover, we must have $\chi(A)=\chi(B)=4$ (otherwise $G'$ is $4$-colourable). By the definition of the SPQR tree, $A+xy$ is either a cycle or is $3$-connected. However, $A+xy$ cannot be a cycle since $\chi(A)=4$. Thus, $A+xy$ is a $3$-connected, as required.

Here are some observations that are slightly too long for a comment. First, note that the claim is false if we replace $5$ by $4$.

Claim. There exists a graph $G$ with $\chi(G)=4$ such that $G$ does not contain a $3$-connected subgraph.

Proof. The Moser Spindle is a well-known graph with chromatic number $4$ (since it is obtained via the Hajo's construction applied to two copies of $K_4$). Moreover, it is easy to see that no subgraph of the Moser Spindle is $3$-connected. $\square$

On the other hand, every graph with chromatic number $4$ contains a subgraph which is 'almost' $3$-connected.

Claim. Every graph $G$ with $\chi(G)=4$ contains a subgraph $A$ and $x,y \in V(A)$ such that $A+xy$ is $3$-connected.

Proof. Let $G'$ be a subgraph of $G$ such that $\chi(G')=4$ and $G'$ is minimal (under the subgraph relation) with this property. If $G'$ is $3$-connected, we are done. Otherwise, let $(A,B)$ be a $(\leq 2)$-separation of $G'$ where $A$ corresponds to a leaf vertex in the SPQR tree of $G'$. By the minimality of $G'$, $\chi(A), \chi(B) \leq 3$. Thus, $(A,B)$ is a $2$-separation and the vertices $x,y \in V(A) \cap V(B)$ must be non-adjacent in $G'$ (otherwise $G'$ is $3$-colourable). Moreover, we must have $\chi(A)=\chi(B)=3$ (otherwise $G'$ is $3$-colourable). By the definition of the SPQR tree, $A+xy$ is either a cycle or is $3$-connected. However, $A+xy$ cannot be a cycle since $\chi(A)=3$. Thus, $A+xy$ is $3$-connected, as required.