Can someone tell me if this is a bipartite graph?

[Topgun_68]

Homework Statement

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

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 :<)

 

[Ray Vickson]

Homework Statement

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

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 :<)

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.

 

[Topgun_68]

Thanks for your feedback!

 

[HallsofIvy]

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

 

[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.

 

[Topgun_68]

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

 

[haruspex]

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

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.

 

[Bacle2]

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.

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.

 

[haruspex]

I think he meant that the graph _cannot be_ bipartite , because it contains a complete graph

No, it's quite clear that HoI thought bipartite meant disconnected:. Note the plural 'edges':

it would be possible to go from any vertex to any other vertex along edges