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

Question

"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?

Answer 1

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.

Answer 2

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.

Answer 3

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.