# How to check that given graph is Bipartite or not?

**URL:** <https://igraph.discourse.group/t/how-to-check-that-given-graph-is-bipartite-or-not/916>\
**Category:** Usage\
**Tags:** R\
**Created:** [21 October 2021 15:56 UTC](https://igraph.discourse.group/t/how-to-check-that-given-graph-is-bipartite-or-not/916 "2021-10-21T15:56:18Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Suresh\_U\_Kore](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/suresh_u_kore/32/608_2.png) [@Suresh\_U\_Kore](https://igraph.discourse.group/u/Suresh_U_Kore)\
**Post date:** [21 October 2021 15:56 UTC](https://igraph.discourse.group/t/how-to-check-that-given-graph-is-bipartite-or-not/916/1 "2021-10-21T15:56:18Z")

</div>

How to check that given graph is Bipartite or not.,? Please provide me R syntax with Graph G=C5. It my kind request

---

<div class="post-metadata">

**Author:** ![Suresh\_U\_Kore](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/suresh_u_kore/32/608_2.png) [@Suresh\_U\_Kore](https://igraph.discourse.group/u/Suresh_U_Kore)\
**Post date:** [22 October 2021 02:06 UTC](https://igraph.discourse.group/t/how-to-check-that-given-graph-is-bipartite-or-not/916/3 "2021-10-22T02:06:59Z")

</div>

Thanks. But when I make graph C5 using g=make\_graph( ) & use is\_bipartite(g) then its not working.

---

<div class="post-metadata">

**Author:** ![Suresh\_U\_Kore](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/suresh_u_kore/32/608_2.png) [@Suresh\_U\_Kore](https://igraph.discourse.group/u/Suresh_U_Kore)\
**Post date:** [22 October 2021 02:26 UTC](https://igraph.discourse.group/t/how-to-check-that-given-graph-is-bipartite-or-not/916/4 "2021-10-22T02:26:37Z")

</div>

When I tried the same for cycle with 4 vertices C4, output is FALSE. But C4 is Bipartite graph. Please clear my doubt.

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [22 October 2021 08:00 UTC](https://igraph.discourse.group/t/how-to-check-that-given-graph-is-bipartite-or-not/916/5 "2021-10-22T08:00:31Z")

</div>

I’m sorry, you’re right. I deleted my post from above so it wouldn’t confuse future readers.

igraph uses the term “bipartite” somewhat idiosyncratically. It mostly applies to graph data structures that have a logical “`type`” vertex attribute, marking each vertex as belonging to one or the other partition. It does not matter if there are edges between two partitions. The function `is_bipartite` will only check if the graph has the `type` vertex attribute, and that’s it.

To decide whether a graph is bipartite, as a mathematician would mean it, you can use `bipartite_mapping()`.

Example:

```auto
> c4 <- make_ring(4)
> bipartite_mapping(c4)
$res
[1] TRUE

$type
[1] FALSE TRUE FALSE TRUE

> c5 <- make_ring(5)
> bipartite_mapping(c5)
$res
[1] FALSE

$type
logical(0)

```

The `$res` component of the result tells you whether the graph is bipartite. The `$type` component gives you a specific partitioning, if this is possible.

---

<div class="post-metadata">

**Author:** ![Suresh\_U\_Kore](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/suresh_u_kore/32/608_2.png) [@Suresh\_U\_Kore](https://igraph.discourse.group/u/Suresh_U_Kore)\
**Post date:** [22 October 2021 11:01 UTC](https://igraph.discourse.group/t/how-to-check-that-given-graph-is-bipartite-or-not/916/6 "2021-10-22T11:01:49Z")

</div>

Thanks a a lot. why $type FALSE TRUE FALSE TRUE is showing? What do you mean by this.? Please clear it sir.  
################  
KORE S.U  
Head  
Dept of Maths,  
S.K.College,Jalkot  
Maharashtra State,  
INDIA

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [22 October 2021 12:31 UTC](https://igraph.discourse.group/t/how-to-check-that-given-graph-is-bipartite-or-not/916/7 "2021-10-22T12:31:32Z")

</div>

The `n`th truth value in the `$types` vector indicates which partition the `n`th vertex belongs to. FALSE = first partition, TRUE = second partition.

---

<div class="post-metadata">

**Author:** ![vtraag](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/vtraag/32/38_2.png) [@vtraag](https://igraph.discourse.group/u/vtraag)\
**Post date:** [22 October 2021 13:08 UTC](https://igraph.discourse.group/t/how-to-check-that-given-graph-is-bipartite-or-not/916/8 "2021-10-22T13:08:19Z")

</div>

Split this topic on 22 October 2021 13:08 UTC

A post was split to a new topic: [Plot Petersen graph](https://igraph.discourse.group/t/plot-petersen-graph/917)