# Can someone tell me if this is a bipartite graph?

1. Apr 28, 2013

### Topgun_68

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:

• ###### Is-bipartite-graph.jpg
File size:
22.5 KB
Views:
77
2. Apr 28, 2013

### Ray Vickson

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.

3. Apr 28, 2013

### Topgun_68

Thanks for your feedback!

4. Apr 29, 2013

### HallsofIvy

Staff Emeritus
"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.

5. Apr 29, 2013

### Bacle2

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.

6. Apr 30, 2013

### Topgun_68

Thanks for all the valuable insights. I have my final exam this Fri so I can use it

7. Apr 30, 2013

### haruspex

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.

8. Apr 30, 2013

### Bacle2

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.

9. Apr 30, 2013

### haruspex

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