# Why is "If every proper subgraph of G is bipartite, then G is bipartite." False

"If every proper subgraph of G is bipartite, then G is bipartite" is apparently false.

I can't think of a justification in my head. I've been going over this, sketching out multiple non-bipartite graphs with all proper subgraphs being Bipartite, but the main graph not. I haven't come up with anything. Can someone help me?

• Maybe a triangle? Nov 27, 2020 at 20:05
• Look at the triangle graph as a tripartite graph. Every subgraph is bipartite, but the triangle can't be made into a bipartite graph. Nov 27, 2020 at 20:06
• Ohh okay thanks Nov 27, 2020 at 20:09
• Note that $G$ has such property iff $G$ has exactly one odd cycle Nov 27, 2020 at 20:14
• @Lelouch ...and nothing else. Nov 28, 2020 at 3:27

## 3 Answers

So I had complicated things too much and forgotten to build up from the basics. A triangle graph would have a bipartite proper subgraph but is itself not bipartite.

You can consider any odd cycle, $$C_{2n+1}$$. Removing an edge you have a $$P_{2n+1}$$ and removing a vertex you have a $$P_{2n}$$. Both are bipartite.

Proof by contradiction. Assume that every non-bipartite graph has a non-bipartite proper subgraph. Then, starting with any non-bipartite finite graph $$G_0$$, say $$G_0=K_5$$, we can get an infinite decreasing sequence of nom-bipartite graphs $$G_0\supset G_1\supset G_2\supset G_3\supset\cdots$$ such that $$G_{n+1}$$ is a proper subgraph of $$G_n$$ for each $$n$$. This is impossible, seeing as the finite graph $$G_0$$ has only a finite number of subgraphs.