95:
85:
64:
31:
382:
22:
476:
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.
539:
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
442:
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.
345:
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
263:
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
228:
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
475:
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
317:
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".
433:
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.
642:
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.
151:
718:
361:
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. —
498:
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. —
622:
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. —
708:
723:
35:
733:
244:
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.
141:
703:
713:
117:
728:
347:
230:
672:
Don't see 'nonempty' in definition, thanks. Usually, 'to divide a set' require non-emptiness of parts, but it has to be said explicitly.
519:
483:
214:
189:
108:
69:
408:
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, --
698:
459:
229:
mathematics. To suggest that graph theory is somehow within 'ubiquitous computing' is therefore inappropriate. John Carter
559:
44:
401:. The method is to use the spanning tree (in red), and to alternate two colors (blue and white) starting at a root
663:
627:
583:
544:
graphs seem to be a counterexample. Also, there isn’t a source to this, and I’m wondering where it came from.
503:
366:
330:
351:
234:
523:
487:
210:
185:
512:
Yes, I think that is sufficient. It is not what I (as a learner) would have needed but it seems correct
413:
50:
574:? It's not "if and only if", and we don't say that it is. There's a source for the same information at
206:
181:
94:
612:
598:
555:
677:
673:
648:
644:
547:
515:
479:
447:
202:
177:
319:
21:
659:
623:
579:
499:
451:
362:
326:
116:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
608:
594:
551:
455:
301:
265:
100:
173:
please add a link to petri-net, as an application of bi-partite graphs. thank you! andrew frank
84:
63:
575:
430:
The reference article rather says "if a graph is bipartite, then its spectrum is symmetric".
409:
269:
593:
No, sorry for the confusion. I was referring to the third bullet point under
Properties.
571:
249:
325:
I disagree with this change. Bipartite graphs should not be required to be connected. —
283:
692:
297:
290:
389:
In case it helps, below is a drawing showing how to partition a connected graph
113:
381:
427:"The spectrum of a graph is symmetric if and only if it's a bipartite graph."
245:
90:
681:
667:
652:
631:
616:
602:
587:
563:
527:
507:
491:
463:
417:
370:
355:
346:
the information there. Any other suggestions to what should be done? --
334:
305:
273:
253:
238:
286:
guideline, the article name "Bipartite graph" is not ambiguous, so the
380:
15:
570:
Are you talking about the degree sum formula in the section
443:
Thus, I have edited the article to use the term "parts".
423:
Bipartite graphs have symmetric spectra, but not conversely
393:
with only even length cycles into two sets of vertices
112:, a collaborative effort to improve the coverage of
576:Handshaking lemma § Bipartite and biregular graphs
385:A graph with only even length cycles is bipartite
658:Where do you see "nonempty" in the definition? —
719:Knowledge level-5 vital articles in Mathematics
8:
296:template is inappropriate. I'll remove it.
513:
477:
58:
709:Knowledge vital articles in Mathematics
60:
19:
724:B-Class vital articles in Mathematics
638:Is a graph with one vertix bipartite?
7:
106:This article is within the scope of
535:Converse of sum of degrees property
282:Good point. In the language of the
49:It is of interest to the following
264:should be removed from this page.
14:
734:Mid-priority mathematics articles
126:Knowledge:WikiProject Mathematics
704:Knowledge level-5 vital articles
129:Template:WikiProject Mathematics
93:
83:
62:
29:
20:
146:This article has been rated as
714:B-Class level-5 vital articles
578:; I'll copy it over to here. —
1:
682:17:37, 25 November 2023 (UTC)
668:17:30, 25 November 2023 (UTC)
653:16:21, 25 November 2023 (UTC)
607:Properties: Characterization
438:Parts of a Multipartite Graph
356:15:19, 27 February 2012 (UTC)
306:10:44, 27 November 2011 (UTC)
274:09:50, 27 November 2011 (UTC)
120:and see a list of open tasks.
729:B-Class mathematics articles
632:16:45, 1 January 2022 (UTC)
617:15:37, 1 January 2022 (UTC)
603:15:36, 1 January 2022 (UTC)
588:05:35, 1 January 2022 (UTC)
564:02:18, 1 January 2022 (UTC)
371:22:02, 27 August 2012 (UTC)
254:04:34, 29 August 2011 (UTC)
239:04:02, 29 August 2011 (UTC)
750:
528:07:19, 1 August 2017 (UTC)
508:07:08, 1 August 2017 (UTC)
492:06:06, 1 August 2017 (UTC)
464:15:41, 23 March 2016 (UTC)
192:) 18:05, 16 February 2006‎
418:08:47, 23 July 2013 (UTC)
335:14:09, 20 June 2012 (UTC)
145:
78:
57:
572:Bipartite graph § Degree
152:project's priority scale
109:WikiProject Mathematics
699:B-Class vital articles
405:of the spanning tree.
386:
217:) 17:22, 10 July 2007‎
384:
36:level-5 vital article
132:mathematics articles
341:Further improvement
471:Testing Algorithms
387:
377:Even length cycles
101:Mathematics portal
45:content assessment
550:comment added by
530:
518:comment added by
494:
482:comment added by
467:
450:comment added by
219:
205:comment added by
194:
180:comment added by
166:
165:
162:
161:
158:
157:
741:
566:
466:
444:
295:
289:
218:
199:
193:
174:
134:
133:
130:
127:
124:
103:
98:
97:
87:
80:
79:
74:
66:
59:
42:
33:
32:
25:
24:
16:
749:
748:
744:
743:
742:
740:
739:
738:
689:
688:
640:
545:
543:
537:
473:
445:
440:
425:
379:
343:
293:
287:
226:
224:Bigraph hatnote
200:
175:
171:
131:
128:
125:
122:
121:
99:
92:
72:
43:on Knowledge's
40:
30:
12:
11:
5:
747:
745:
737:
736:
731:
726:
721:
716:
711:
706:
701:
691:
690:
687:
686:
685:
684:
660:David Eppstein
639:
636:
635:
634:
624:David Eppstein
591:
590:
580:David Eppstein
541:
540:disconnected K
536:
533:
532:
531:
510:
500:David Eppstein
472:
469:
439:
436:
424:
421:
378:
375:
374:
373:
363:David Eppstein
348:80.202.100.133
342:
339:
338:
337:
327:David Eppstein
316:
313:
311:
310:
309:
308:
277:
276:
259:
257:
256:
231:89.204.177.130
225:
222:
221:
220:
170:
167:
164:
163:
160:
159:
156:
155:
144:
138:
137:
135:
118:the discussion
105:
104:
88:
76:
75:
67:
55:
54:
48:
26:
13:
10:
9:
6:
4:
3:
2:
746:
735:
732:
730:
727:
725:
722:
720:
717:
715:
712:
710:
707:
705:
702:
700:
697:
696:
694:
683:
679:
675:
671:
670:
669:
665:
661:
657:
656:
655:
654:
650:
646:
637:
633:
629:
625:
621:
620:
619:
618:
614:
610:
605:
604:
600:
596:
589:
585:
581:
577:
573:
569:
568:
567:
565:
561:
557:
553:
549:
534:
529:
525:
521:
517:
511:
509:
505:
501:
497:
496:
495:
493:
489:
485:
481:
470:
468:
465:
461:
457:
453:
449:
437:
435:
431:
428:
422:
420:
419:
415:
411:
406:
404:
400:
396:
392:
383:
376:
372:
368:
364:
360:
359:
358:
357:
353:
349:
340:
336:
332:
328:
324:
323:
322:
321:
314:
307:
303:
299:
292:
285:
281:
280:
279:
278:
275:
271:
267:
262:
261:
260:
255:
251:
247:
243:
242:
241:
240:
236:
232:
223:
216:
212:
208:
204:
197:
196:
195:
191:
187:
183:
179:
168:
153:
149:
143:
140:
139:
136:
119:
115:
111:
110:
102:
96:
91:
89:
86:
82:
81:
77:
71:
68:
65:
61:
56:
52:
46:
38:
37:
27:
23:
18:
17:
641:
606:
592:
546:— Preceding
538:
520:82.83.186.53
514:— Preceding
484:82.83.186.53
478:— Preceding
474:
446:— Preceding
441:
432:
429:
426:
407:
402:
398:
394:
390:
388:
344:
315:
312:
258:
227:
207:87.12.170.59
201:— Preceding
182:82.218.14.12
176:— Preceding
172:
148:Mid-priority
147:
107:
73:Mid‑priority
51:WikiProjects
34:
410:MathsPoetry
123:Mathematics
114:mathematics
70:Mathematics
693:Categories
674:Spectorsky
645:Spectorsky
169:Petri nets
320:jaydee000
39:is rated
560:contribs
548:unsigned
516:unsigned
480:unsigned
460:contribs
452:Hpfister
448:unsigned
298:Melchoir
215:contribs
203:unsigned
190:contribs
178:unsigned
284:WP:NAMB
150:on the
41:B-class
609:Bbk001
595:Bbk001
552:Bbk001
266:Wicko3
198:Done.
47:scale.
246:McKay
28:This
678:talk
664:talk
649:talk
628:talk
613:talk
599:talk
584:talk
556:talk
524:talk
504:talk
488:talk
456:talk
414:talk
397:and
367:talk
352:talk
331:talk
302:talk
270:talk
250:talk
235:talk
211:talk
186:talk
291:For
142:Mid
695::
680:)
666:)
651:)
630:)
615:)
601:)
586:)
562:)
558:•
526:)
506:)
490:)
462:)
458:•
416:)
369:)
354:)
333:)
304:)
294:}}
288:{{
272:)
252:)
237:)
213:•
188:•
676:(
662:(
647:(
626:(
611:(
597:(
582:(
554:(
542:3
522:(
502:(
486:(
454:(
412:(
403:r
399:V
395:U
391:G
365:(
350:(
329:(
300:(
268:(
248:(
233:(
209:(
184:(
154:.
53::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
