ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a finite simple graph. Say that GG is 55-connected if ∣V(G)∣≥6|V(G)| \ge 6 and, for every set S⊆V(G)S \subseteq V(G) with ∣S∣≤4|S| \le 4, the graph G−SG - S is connected. Say that GG contains a subdivision of K5K_5 if there exist five distinct vertices v1,…,v5∈V(G)v_1, \dots, v_5 \in V(G) (the branch vertices) and ten paths PijP_{ij} in GG, one for each pair 1≤i<j≤51 \le i < j \le 5, such that PijP_{ij} has endpoints viv_i and vjv_j, and any two of these paths meet only in the branch vertices that are common endpoints of the two paths; equivalently, GG has a subgraph obtained from K5K_5 by replacing each edge with an internally disjoint path of length at least 11.

Then every 55-connected graph GG that is not planar contains a subdivision of K5K_5.

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.