-1
$\begingroup$

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

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

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.