Find a Graph with 6 vertices and 12 edges that contains no subgraph isomorphic to $K_{3,3}$. Rigorously prove your answer is correct.
So the answer here is obvious, I think. Take $C_6$ and then inscribe 2 triangles to get a graph $G$ looking something like this:
I had initially tried to argue that since $K_{3,3}$ must contain $C_6$ and that taking any additional edge from this graph along with a subgraph isomorphic to $C_6$ would yield an odd length cycle. Since $K_{3,3}$ is a bipartite graph it cannot contain an odd cycle thus the graph $G$ does not contain a subgraph isomorphic to $K_{3,3}$. This is clearly false, however, since the following illustration demonstrates a graph containing $C_6$ and a 7th edge without an odd cycle.
The actual proof should involve an argument about taking 2 groups of any three vertices and noting that one connection between them is missing required to complete the bipartite graph, but this argument shouldn't be made haphazardly. My question is then: how would one write an correct argument based on this idea both cleanly and formally?
Best Answer
To check if $G$ has a $K_{3,3}$ subgraph, we need to see if it's possible to choose a set $S$ of three vertices of $G$ (forming one side of $K_{3,3}$) and a set $T$ of three other vertices of $G$ (forming the other side of $K_{3,3}$) such that all $9$ edges between $S$ and $T$ are present.
This can be done by brute force: there are only $\binom63$ choices for $S$, and then $T$ must consist of the remaining $3$ vertices. In fact, because nothing changes if we switch $S$ and $T$, we only need to consider $\frac12\binom63$ choices for $S$, and we could probably narrow things down even more if we consider the symmetry of $G$.
But one way to quickly see that no such choice is possible is to notice that vertices $1$ and $4$ must both be in $S$ or both in $T$, since there is no edge between them, and the same is true for the pairs $\{2,5\}$ and $\{3,6\}$. But we'd need an even number of vertices in $S$ and $T$ to keep all three of these pairs together; when $|S|=|T|=3$, we are forced to split up one of the pairs.
(I only mention brute force to point out that while being clever is helpful, it is not required to solve this problem.)