4
$\begingroup$

I would like to decide whether the following graph is bipartite or not:

enter image description here

One way to do this is to determine its chromatic number first, which is obviously $2$, and since every graph with chromatic number $2$ is bipartite, we'd have our answer.

Another way to do this would be to use the fact that every cycle in a bipartite graph has even length. I don't see why this should be true in this case though, so I might have a misunderstanding about what a cycle actually is.

For example, when I start at the top left of the outer square, then I go into the inner square and walk around it, then I leave it at the bottom left and close the cycle by walking to the top left vertex again. But in this case, the cycle would consist of $7$ vertices, because I have to count the vertex where I started twice (since it's the same vertex where I end). So, I would have found an odd cycle here, and this contradicts my observations from before.

What is wrong here?

$\endgroup$

1 Answer 1

6
$\begingroup$

When counting the length of a cycle, you do not count the starting/final vertex twice.

$\endgroup$
3
  • 1
    $\begingroup$ +1 It's better to think in terms of counting the edges rather than the vertices. The OP almost realizes that when he says "count the edge where I started twice" but is thinking about counting the vertex twice. $\endgroup$ Sep 16, 2017 at 12:52
  • $\begingroup$ Woops, I switched edges and vertices here. I actually meant to count the vertices. But the answer provided here is useful anyway, thanks! $\endgroup$
    – Julian
    Sep 16, 2017 at 13:11
  • 1
    $\begingroup$ @Julian If you count vertices and edges correctly, then a cycle has the same number of both. $\endgroup$
    – Arno
    Sep 16, 2017 at 13:24

You must log in to answer this question.

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