Graph with expansion of $K_5$ has subgraph which is expansion of $K_{3,3}$.

154 Views Asked by At

Just wondering how my proof looks...

Statement: if a nonplanar graph has $v \geq 6$, connectivity $c \geq 3$, and a subgraph which is an expansion of $K_5$, then it also has a subgraph which is an expansion of $K_{3,3}$ (the 'utility' graph consisting of 3 houses all 3 of which are connected to 3 utility companies but not to each other).

Proof: We know an expansion introduces vertices with degree 2, and so if $c \geq 3$ as given, then an expanded vertex must have an additional edge connected to it (else we erase the two adjacent vertices and are left with a disconnected vertex, implying $c \leq 2$).

Additionally, this edge must be connected to another vertex in the $K_5$ expansion (if it were connected to two vertices in $K_5$ and one vertex outside $K_5$ we would remove the outside vertex and have a disconnected graph).

Now, we can then form $K_{3,3}$ by choosing the expanded vertex to be a utility, and 3 of its adjacent vertices part of the $K_5$ expansion to be the houses. Of course, since $K_5$ is complete we can find two more houses and utilities since there are paths between each vertex.

This does not give us a graph isomorphic to $K_{3,3}$, but isomorphic to an expansion, because it may be the case that between the original $K_5$ vertices, there are expanded vertices.

1

There are 1 best solutions below

1
On

I don't think the proof of the OP works, to see why look at the comment section.


Proof :

First, we consider the case when no expanded vertices are present in $K_5$, it is necessary to have at least another vertex but we can have as many as we want, anyway we must check if the new component created preserves $c \geq 3$, the only way to make sure this happens is to connect $3$ vertices of $K_5$ to the new component each with at least an edge, it's easy to see how to construct a $K_{3,3} $-expanded from that.

Now, It is easy to prove that $K_{3,3} $-expanded is a subgraph if one of the following facts happens:

  • If two expanded vertices on different edges are connected with a path composed by edges all not included in $K_5$.
  • If a expanded vertex is connected to a vertex of $K_5$ with a path composed by edges all not included in $K_5$.

Now we'll see that this always happens : say you have a expanded vertex on $K_5$, then you need to connect it to another vertex: if this vertex belongs to $K_5$ we are done, otherwise if it is a vertex belonging to another component, this component has to be connected to $K_5$ with at least $3$ vertices so we will have the first fact (connection to a expanded vertex on different edge) or the second fact (connection to a vertex of $K_5$) satisfied. Otherwise, if it is connected to another expanded vertex on another edge then the first fact is satisfied.

Note that connecting all expanded vertices on the same edge with a vertex not included in $K_5$ or connecting one to each other does not preserve $c \geq 3$ because it's easy to see that $c=2$ in this case.


If someone finds something wrong don't hesitate to write a comment!