Maximal graph not containing a subdivision of $K_5$ is $2$-connected?

80 Views Asked by At

I am trying to prove that a graph not containing no subdivisions of $K_5$, such that the addition of any edge would result in the existence of such a subdivision, is $2$-connected.

I already know the graph must be connected, so the missing result is to prove that the graph cannot contain a cut vertex.

My approach is to suppose it has a cut vertex separating the graph into $H_1$ and $H_2$. Since for any main vertex of a subdivision of $K_5$, there exist at least $3$ disjoint paths linking them, one can prove that the main vertices of the subdivision must lie in the same component, say $H_1$. But why is this impossible?

1

There are 1 best solutions below

0
On

Let $v$ be a cut vertex and $V_1,V_2$ a non-trivial partition of $V ∖ \{v\}$ with no edges from vertices in $V_1$ to vertices in $V_2$. look at edges from cut vertex $v$ to $V_1$, lets say $w_1 \in V_1$ is connected to $v$, similarly find $w_2 \in V_2$ which is connected to $v$, Now connect $w_1$ with $w_2$ by an edge then this will create a subdivision of $K_5$ according to the property given in the question and all corresponding degree $4$ vertices wont be in $V_1$ or $V_2$ because the path created by the edge $(w_1,w_2)$ is a path from $w_1$ to $v$ which is a subdivision of the edge $(w_1,v)$ and the edge $(w_1,v)$ is already present. Hence a subdivision of $K_5$ wont be created with all degree $4$ vertices in $V_1$ by the edge $(w_1,w_2)$. Hence by the addition of the edge $(w_1,w_2)$ a subdivision of $K_5$ is created with some degree $4$ vertices in $V_1$ and some in $V_2$. Now take a vertex $a \in V_1$ and $b \in V_2$ which are two degree $4$ vertices in the subdivision created. There are at least $3$ disjoint paths from $a$ to $b$. Only one of them passes through $v$ and another passes though $(w_1,w_2)$ and one more path not using $v,(w_1,w_2)$ is present resulting in a contradiction that $v$ is a cut vertex. hence $2$-connected