Talk:Bipartite graph

Petri nets

please add a link to petri-net, as an application of bi-partite graphs. thank you! andrew frank — Preceding unsigned comment added by 82.218.14.12 (talk • contribs) 18:05, 16 February 2006‎

Done. — Preceding unsigned comment added by 87.12.170.59 (talk • contribs) 17:22, 10 July 2007‎

Bigraph hatnote

I think the heading "For the ubiquitous computing formalism, see bigraph" should be removed. One reason is that the link to 'bigraph' mis-represents what a bi-partite graph is! The second reason is that 'ubiquitous computing' seems a very wooly area whereas Graph Theory aims to be a precise part of mathematics. To suggest that graph theory is somehow within 'ubiquitous computing' is therefore inappropriate. John Carter 89.204.177.130 (talk) 04:02, 29 August 2011 (UTC)

That heading is just a kindness to people looking for the computing concept who came here by accident. It doesn't imply there is any actual connection. McKay (talk) 04:34, 29 August 2011 (UTC)

It is necessary to link from "Bigraph" to "Bipartite graph" because a bipartite graph is sometimes called a bigraph, and hence confusion could result. But the reverse is not so: nobody would ever refer to a bigraph as a bipartite graph. There is no confusion, so I believe the disambiguating heading should be removed from this page. Wicko3 (talk) 09:50, 27 November 2011 (UTC)

Good point. In the language of the WP:NAMB guideline, the article name "Bipartite graph" is not ambiguous, so the {{For}} template is inappropriate. I'll remove it. Melchoir (talk) 10:44, 27 November 2011 (UTC)

I agree with McKay that the heading is useful and should stay. Also, a bipartite graph is a subset of the class of connected graphs and that fact should appear in its definition. I added that stipulation, but no entry exists for "connected graph". jaydee000

I disagree with this change. Bipartite graphs should not be required to be connected. —David Eppstein (talk) 14:09, 20 June 2012 (UTC)

Further improvement

This article contains almost all necessary information and enough references to be a good article, however the article is somewhat messy, and there is no good flow in it. Should someone feel the need to improve this article, it should be done by rewriting it for better readability while preserving the information there. Any other suggestions to what should be done? --80.202.100.133 (talk) 15:19, 27 February 2012 (UTC)

I think a lot of the flow problems had to do with bad section ordering. I've reordered the sections and am now working on improving the writing and sourcing within the sections. —David Eppstein (talk) 22:02, 27 August 2012 (UTC)

Even length cycles

A graph with only even length cycles is bipartite

In case it helps, below is a drawing showing how to partition a connected graph G with only even length cycles into two sets of vertices U and V. The method is to use the spanning tree (in red), and to alternate two colors (blue and white) starting at a root r of the spanning tree.

This drawing can be used in a demonstration that a graph is bipartite if and only if all its cycles are of even length. Best, --MathsPoetry (talk) 08:47, 23 July 2013 (UTC)

Bipartite graphs have symmetric spectra, but not conversely

"The spectrum of a graph is symmetric if and only if it's a bipartite graph."

The reference article rather says "if a graph is bipartite, then its spectrum is symmetric".

A triangle (i.e. complete graph on 3 vertices) has symmetric spectrum (as does any undirected graph as mentioned elsewhere on the wikipage) but it is not a bipartite graph, since it has an odd cycle. Thus, the converse is not true.

Parts of a Multipartite Graph

The first use I've seen of the term "partite sets" is in this article. Historically, the sets U and V are called the "parts" of the graph. To check this, I googled "partite sets" and found about 12,000 references whereas the much longer term "parts of a bipartite graph" has about 93,000 references. Thus, I have edited the article to use the term "parts". — Preceding unsigned comment added by Hpfister (talk • contribs) 15:41, 23 March 2016 (UTC)

Testing Algorithms

Please add a clarification (I don't feel up to that myself) that when testing for bipartite graphs using depth-first or breadth-first search one has to take into account the possibility of disconnected graphs. In that case such an algorithm will only check the connected component that is reachable from the starting vertex. So in order to correctly determine if a given graph is bipartite one has to make sure that all vertices are actually visited, for example by maintaining a count of visited vertices or by actually removing edges from the datastructure and reiterate while there are edges left. — Preceding unsigned comment added by 82.83.186.53 (talk) 06:06, 1 August 2017 (UTC)

I changed "depth first search tree" to "depth first search forest" etc in that section. I don't think anything more than that needs to be done to handle disconnected graphs. —David Eppstein (talk) 07:08, 1 August 2017 (UTC)

Yes, I think that is sufficient. It is not what I (as a learner) would have needed but it seems correct — Preceding unsigned comment added by 82.83.186.53 (talk) 07:19, 1 August 2017 (UTC)

Converse of sum of degrees property

Here we say that a graph is bipartite if and only if its vertices can be partitioned into sets A and B such that the sum of the degrees of vertices in each partition is equal, and any vertex’s degree is less than or equal to the cardinality of the other set. I don’t see why this converse is true. Two disconnected K₃ graphs seem to be a counterexample. Also, there isn’t a source to this, and I’m wondering where it came from. — Preceding unsigned comment added by Bbk001 (talk • contribs) 02:18, 1 January 2022 (UTC)

Are you talking about the degree sum formula in the section Bipartite graph § Degree? It's not "if and only if", and we don't say that it is. There's a source for the same information at Handshaking lemma § Bipartite and biregular graphs; I'll copy it over to here. —David Eppstein (talk) 05:35, 1 January 2022 (UTC)

No, sorry for the confusion. I was referring to the third bullet point under Properties. Bbk001 (talk) 15:36, 1 January 2022 (UTC)

Properties: Characterization Bbk001 (talk) 15:37, 1 January 2022 (UTC)

Oh, I see. That looks likely to be incorrect to me, and it's definitely unsourced. I'll remove it, and the non-characterization (upper bound on #edges) in the next bullet. —David Eppstein (talk) 16:45, 1 January 2022 (UTC)

Is a graph with one vertix bipartite?

Consider a simple graph with the only vertix (obviously, it is empty). It has no an odd cycle (no cycles at all), but it is not bipartite, because one vertix cannot be diuvided onto two disjoined nonempty parts. Spectorsky (talk) 16:21, 25 November 2023 (UTC)

Where do you see "nonempty" in the definition? —David Eppstein (talk) 17:30, 25 November 2023 (UTC)

Don't see 'nonempty' in definition, thanks. Usually, 'to divide a set' require non-emptiness of parts, but it has to be said explicitly. Spectorsky (talk) 17:37, 25 November 2023 (UTC)