# Find a Graph with 6 vertices and 12 edges that contains no subgraph isomorphic to $K_{3,3}$

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?

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.)

You need to remove 3 edges from your graph $G$ to get a $K_{3,3}$. $K_{3,3}$ does not contain a $K_3$, and your original graph contains 8 $K_3$'s. By removing an edge, you at most destroy 2 $K_3$'s.

• The "original graph" is $K_6$ from which the 3 edges critical to forming any $K_{3,3}$'s were removed. My professor has already confirmed the graph provided is the correct answer. I am looking only for justification that relies only on the graph $G$ provided as an answer. – rjm27trekkie Sep 18 '18 at 22:01
• I mean, you need to remove 3 edges from the graph you provided to get a $K_{3,3}$. I am trying to argue that the removal to $K_{3,3}$ is impossible. – Hw Chu Sep 18 '18 at 22:03
• I like that argument a lot actually. I'm also really looking for clarification of what my professor's idea would have been, but that's a lot more clever i think. Could you maybe help me to understand what he was thinking with considering grouping 2 sets of 3 vertices? – rjm27trekkie Sep 18 '18 at 22:15
• I guess that is something like Misha's post ;-). – Hw Chu Sep 18 '18 at 22:29
• yes misha's "way to quickly see" is what i was trying to remember. – rjm27trekkie Sep 19 '18 at 2:39