Questions tagged [bipartite-graphs]

For questions about graphs with two sets of distinct vertices in which edges join vertices from different sets.

395 questions
19 views

How does one find a 2-partitioning of a graph where both sets of nodes are fully connected?

Let's suppose I have a graph $G=(V_1 \cup V_2, E)$. Furthermore I know that $\forall v_1 \in V_1, v_2 \in V_2 . (v_1, v_2) \in E$. But nodes in each sets can also have edges and both sets are ...
30 views

Maximal Matching in Bipartite Graphs

Maximal matching for a Biparitie Graph is the maximum cardinality set of edges such that no two edges share any vertex. We are given a biparitie graph and let's say there is only one edge $E$ that ...
21 views

How to find if we can construct a bi-partite graph with the information about the degree of vertices?

Say there are two sets X and Y,which denote the degree of vertices of the bi partite graph. Say X = {2,2,1} and Y = {2,3},with this information about the degree of vertices,how to tell if we can ...
292 views

Spanning forests of bipartite graphs and distinct row/column sums of binary matrices

Let $F_{m,n}$ be the set of spanning forests on the complete bipartite graph $K_{m,n}$. Let $$S_{m,n} = \{(r(M), c(M)), M \in B_{m,n} \}$$ where $B_{m,n}$ is the set of $m \times n$ binary matrices ...
56 views

Bounding the number of edges in a graph satisfying a certain property

I am going through past papers because I am revising for my Graph Theory exam this week. I encountered the following question: The bipartite Ramsey number $R(s,t)$ is the minimum $n$ s.t. a ...
19 views

19 views

Maximum Matching in a bipartite graph

Can somebody clearly explain me the below problem of finding maximum matching in a bipartite graph? How the vertices are entered in queue? How they choose augment? Are they choosing augment ...
32 views

bipartite subgraph H

Let H be a maximum bipartite subgraph of G. The bipartition divides the vertices of H (and G) into two sides, L and R. Prove that every vertex v has the property that (according to G) at least half of ...
16 views

Why that a graphon is bipartite iff its odd cycle density is 0?

In the book "large networks and graph limits", exercise 7.16 is the question in the title. Let W be a graphon which its all odd cycle homomorphism density is 0. By proposition 14.21, W is a limit of ...
34 views

Lower bound of number of independent sets

Let $G$ be a connected regular graph with even number of vertices $v$. Also let $i_{v/2}(G)$ be the number of independent sets of $G$ of size $\frac{v}{2}$. Is it possible that $i_{v/2}(G)> 2^{v/2}$...
30 views

Prove that if G — (V, E) is an arbitrary bipartite graph, then $|E| \leq |V|^2/4$ using induction [duplicate]

let $n=\mid V\mid$ base case: let $n=0$. Thus lemma becomes vacuously true since both bipartitions will contain the empty set thus not a bipartite graph. Inductive step: let $k\in\mathbb{N}$, ...
51 views

graph theory problem - containing $K_{2,m}$

I have a graph theory problem that I can't figure out how to solve. The problem is: Prove that if $G$ is a simple graph with $n$ vertices and $$\sum_{v\in V(G)}\binom{d(v)}{2} > (m-1)\binom{n}{2}$$...
21 views

14 views

Must a bipartite graph be simple?

Are all bipartite graphs simple i.e. is being simple a requirement for a graph to be considered bipartite? Most definitions don't mention anything about it, however the following definition of a ...
23 views

Does this type of tripartite graph formed from two $K_{2,4}$'s have a name?

This tri-partite graph is a $K_{4,2}$ (blue) followed by another $K_{4,2}$ (red): I used red and blue just because when I used blue both times, it might look like some of the leftmost vertices are ...
Perhaps the most common term for each of the two disjoint sets in a bipartite graph is "part". So I can say for example: One "part" of the $K_{4,4}$ connects to a corresponding "part" of a ...