# Is this a bug between RelationGraph and BipartiteGraphQ?

Inspired by yode's latest question I was playing around with RelationGraph and found that BipartiteQ seems to be unable to detect certain bipartite results.

As an example, I was looking at the graph where each vertex is a 1- or 2-digit integer, and edges indicate whether a 2-digit integer starts or ends with a 1-digit integer. This is clearly a bipartite graph (and GraphLayout -> "BipartiteEmbedding" shows this), since there are no edges between 2-digit numbers and no edges between single digits. And up to n = 19 this works fine:

g = RelationGraph[(StringEndsQ[#1, #2] || StringStartsQ[#2, #])
&& # != #2 &, ToString /@ Range[0, 19],
GraphLayout -> "BipartiteEmbedding", VertexLabels -> "Name"]


BipartiteGraphQ @ g
(* True *)


But as soon as I get to 20:

g = RelationGraph[(StringEndsQ[#1, #2] || StringStartsQ[#2, #])
&& # != #2 &, ToString /@ Range[0, 20],
GraphLayout -> "BipartiteEmbedding", VertexLabels -> "Name"]


BipartiteGraphQ @ g
(* False *)


The problem seems to be something internal to the result of RelationGraph, since extracting the edges and reconstructing the graph works:

BipartiteGraphQ @ Graph @ EdgeList @ g
(* True *)


We can however localise the problem a bit by computing the graph on a smaller set of vertices. It's possible to remove all but 6 vertices/edges and still reproduce the problem:

g = RelationGraph[(StringEndsQ[#1, #2] || StringStartsQ[#2, #])
&& # != #2 &, ToString /@ {0, 1, 2, 10, 12, 20},
GraphLayout -> "BipartiteEmbedding", VertexLabels -> "Name"]


BipartiteGraphQ @ g
(* False *)


Removing any further edges "resolves" the problem.

Is this a bug in BipartiteGraphQ? Am I misunderstanding something about bipartite graphs?

I'm using Mathematica 10.4 on Windows 10.

• See the end of my answer here: mathematica.stackexchange.com/a/109437/12 – Szabolcs Apr 5 '16 at 12:01
• @Szabolcs Ah okay, so it's a known issue. Interestingly, in all the cases I've tried, GraphLayout -> "BipartiteEmbedding" still worked without an issue. – Martin Ender Apr 5 '16 at 12:04
• BTW I reported that as CASE:3531918 on Feb 13 and they told me that the problem was already known. I didn't read your post in detail and I don't know if it is the same bug. I also complained here: chat.stackexchange.com/transcript/2234?m=27550013#27550013 – Szabolcs Apr 5 '16 at 12:06
• BTW IGraph/M has IGBipartiteQ precisely for this reason. <del>But you should know that it is much slower than the built-in function because converting a Mathematica graph to an igraph one is a huge overhead.</del> ... Well, I just tested, and for huge graphs it is in fact faster than BipartiteGraphQ despite that conversion overhead!! – Szabolcs Apr 5 '16 at 12:28
• Just for the record, this can still be reproduced in 11.0. – Martin Ender Sep 15 '16 at 8:43