1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can someone tell me if this is a bipartite graph?

  1. Apr 28, 2013 #1
    1. The problem statement, all variables and given/known data

    I know this is the description of a bipartite graph:

    A bipartite graph G is a simple graph whose vertex set can be partitioned into two mutually disjoint nonempty subsets V1 and V2 such that vertices in V1 may be connected to vertices in V2, but no vertices in V1 are connected to other vertices in V1 and no vertices in V2 are connected to other vertices in V2


    3. The attempt at a solution

    Since a simple graph has no loops or parallel edges, than the attached photo must not be a bipartite graph, correct? Thanks for any feedback!

    My scanner is broke so I apologize for the lame drawing :<)
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     

    Attached Files:

  2. jcsd
  3. Apr 28, 2013 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You are correct: the graph is not bipartite. If it were bipartite, v1 would be in some subset A of nodes. Now v3 and v4 are connected to v1 by arcs, so {v3,v4} would have to be in another node subset B; but v3 and v4 are also connected by an arc, so we cannot have them in the same subset---contradiction.
     
  4. Apr 28, 2013 #3
    Thanks for your feedback!
     
  5. Apr 29, 2013 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    "Bipartite" means "two parts". Your graph is NOT bipartite because it does not consist of two separate parts. The fact that it would be possible to go from any vertex to any other vertex along edges is a clear sign of that.
     
  6. Apr 29, 2013 #5

    Bacle2

    User Avatar
    Science Advisor

    Notice that your graph on n vertices contains a complete (sub)graph on n vertices. A complete graph on n verices cannot be bipartite, almost by definition.
     
  7. Apr 30, 2013 #6
    Thanks for all the valuable insights. I have my final exam this Fri so I can use it :approve:
     
  8. Apr 30, 2013 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, that's not what's meant by a bipartite graph. The key definition is the one Ray Vickson used: that the vertices can be partitioned into two sets such that no edges join two vertices in the same set. As far as I am aware, there is no requirement for the graph to be simple - it could have parallel edges, but no loops, of course.
    An equivalent definition is that there are no odd cycles. Ray indicates a cycle length 3.
     
  9. Apr 30, 2013 #8

    Bacle2

    User Avatar
    Science Advisor

    I think he meant that the graph _cannot be_ bipartite , because it contains a complete graph
    ( I basically repeated what he said without noticing --sorry HOIvy ), which makes it impossible to separate the vertices into two sets S1, S2 , so that there are no edges joining any s_i to s_i' in
    S_i ; i=1,2. Equivalently,given any possible partition of the set S of vertices into S1,S2 , given
    the existence of the complete subgraph K4 , there will necessarily be some edges joining _any_ two vertices vi,vj in either S1 and/or S2.

    Good luck on the test, Top Gun.
     
  10. Apr 30, 2013 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, it's quite clear that HoI thought bipartite meant disconnected:. Note the plural 'edges':
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Can someone tell me if this is a bipartite graph?
Loading...