Graph Theory subgraph K3 3 or K5
I'm having trouble with the two graphs below. I am supposed to find a sub graph of K3,3 or K5 in the two graphs below. Graph #3 appears that it would have a subgraph that is K3,3 however I can't see how the vertices will connect in the same fashion.
4 appears like it will have a K5 however like the previous graph the vertices do not connect in the same fashion. In a K5 graph, all the vertices are connected. How do these graphs have a K3,3 or K5?
2 Answers
$\begingroup$The first graph has $K_{3,3}$ as a subgraph, as outlined below as the "utility graph", and similarly for $K_5$ in the second graph:
You may have been led astray. The graph #3 does not have a $K_{3,3}$ subgraph. Let's prove it!
First, the graph is naturally split up into two, five-vertex subgraphs. Since $K_{3,3}$ has six vertices, we can assume that if there is a $K_{3,3}$ subgraph then one of its vertices must lie in, say, the left subgraph. Let's label the vertices $1,2,3,4$, and $5$, where we start at the top vertex and move clockwise, labeling the center vertex $5$. Apply the same labeling to the right subgraph with the labels $1',2',3',4',$ and $5'$.
Now, can $1$ be in our $K_{3,3}$? Well, if it were, so would $2,4$, and $1'$. However, there is no vertex other than $1$ that connects to both $2$ and $1'$. So, $1$ isn't a vertex. Since this same argument can be carried out for vertices $1,1',3,$ and $3'$, this implies that $\{2,4,5,2',4',5'\}$ is the vertex set for our $K_{3,3}$, which can be checked to fail.
Try to use this method of identifying "problem" vertices in #4 and see if you can prove whether or not it has a $K_{5}$.
Note: if you're attempting to prove these graphs are non-planar, note that we must consider subdivisions of $K_{3,3}$ and $K_5$. As @Couchy311 and @Fabio Somenzi point out, such subdivisions do exist.
$\endgroup$ 0
