-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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .