Suppose you are given a bipartite graph (L, R, E), where L denotes the vertices

Question

Suppose you are given a bipartite graph (L, R, E), where L denotes the vertices on the left, R denotes the vertices on the right and E denote the set of edges.

Furthermore it is given that degree of every vertex is exactly d (you may assume that d > 0).

We will construct a flow network G using this bipartite graph in the following manner: G has |L| + |R| + 2 vertices.

There is a vertex corresponding to every vertex in L and R. There is also a source vertex s and a sink vertex t.

There are directed edges with weight 1 from s to all vertices in L and directed edges of weight 1 from all vertices in R to t.

For each edge (u, v) ? E, there is a directed edge from u to v with weight 1 in G.

(The figure below shows an example of a bipartite graph and the construction of the network.)

Argue that for any given bipartite graph where the degree of every vertex is the same nonzero value d, there is an integer s-t flow (i,e., flow along any edge is an integer) in the corresponding network with value |L|.

Explanation / Answer

In bipartitie graph, normally we will have set of odd and even degree vertices. It has minimum degree 1 for each vertex in bi-partite graph.

So if degree for each vertex is same, it means bi-partite graph all vertices are connected with each other. So for every vertex, there was an sink vertex. So there will be an integer s-t flow.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.