Questions tagged [bipartite-graphs]

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

0
votes
0answers
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 ...
3
votes
2answers
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 ...
1
vote
0answers
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 ...
13
votes
3answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
19 views

Can a $k$-regular graph with $99$ vertices $(G=(99,E))$ be a bipartite graph?

I was reviewing some exams from previous years on Graph Theory and I'm stuck on this question. What I have so far is that for a graph to be bipartite, we need to have $2$ subsets of $V=99$ $(G=(V,E)...
0
votes
0answers
18 views

Finding a Hamiltonian Cycle from a perfect matching on a the bipartite graph

A disjoint vertex cycle cover can be found by a perfect matching on the bipartite graph constructed from the original graph (L) and its copy (R) and with L original graph edges replaced by ...
5
votes
1answer
204 views

Bipartite graphs from permutations

Given are $n\geq 1$ permutations of $abcd$. We construct a bipartite graph $G_{a,b}$ as follows: The $n$ vertices on one side are labeled with the sets containing $a$ and the letters after it in each ...
0
votes
0answers
7 views

Maximal matching in bipartite graphs using strong network decomposition

I have been struggling to come up with a way to efficiently do maximal matching in parallel. I tried using a strong network decomposition, solving the problem locally for each component, both in ...
0
votes
0answers
12 views

Connectivity property between k and k+1 connectivity

Following an older question of mine Maximum connected components after removing 2 vertices. It turns out that for the family of graphs I talk about, we can have 1,2 or 3 connected components after the ...
1
vote
1answer
25 views

Bipartite Graph n-1 matchings

Let $K_n$ be partitioned into $n−1$ perfect matchings. We have $n$ teams in a soccer match: on each of $n − 1$ days, $n$ teams pair up according to the day’s perfect matching, i.e. each of the $\frac ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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}$...
0
votes
1answer
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}$, ...
1
vote
1answer
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}$$...
0
votes
2answers
21 views

Help formulating a conjecture about the parity of every cycle length in a bipartite graph and proving it

I know a cycle in a graph $G=(V,E)$ is a sequence of vertices $$v_0, v_1,\ldots, v_k$$ such that $k\geq 3$, $v_k = v_0$, and $G$ contains every edge between consecutive vertices: $(v_0, v_1)$, $(v_1, ...
0
votes
1answer
23 views

Graph which is Bipartite, has an Euler circuit, but not a Hamiltonian circuit

Is there a graph which is bipartite, has an Euler circuit, but not a Hamiltonian circuit? I know the answer is yes, but if you consider something like this: I don't think this would be bipartite, ...
0
votes
0answers
48 views

Generalized Bipartite Matching

Given a bipartite graph with two sets of vertices $L$ and $R$ and some edges $E$ between $L$ and $R$, describe how to produce the largest set of pairings such that a vertex may be paired with at most ...
0
votes
1answer
41 views

Prove that every simple graph $G$ contains a spanning subgraph, which is bipartite and $\deg(v') \geq \frac{1}{2}\deg(v)$.

(i) Prove that every finite simple graph $G$ contains a spanning subgraph $H$ (i.e., $V (G) = V (H)$) such that $H$ is a bipartite graph, and for every vertex $x \in V(G)$, the degree of $x$ in $H$ ...
4
votes
1answer
55 views

Graph on $n$ vertices, each vertex of degree 3 or less. Can we color the vertices in a way such that…

Let $G$ be a graph on $n$ vertices. Suppose each vertex has at most 3 neighbors. Prove that you can color the vertices either red or blue in such a way that each vertex is connected to at most 1 ...
0
votes
1answer
41 views

How can I prove that this two statements are equivalent?

Given: complete graph G and I a list assignment for G prove: G has proper coloring $\Leftrightarrow $ $ \forall \;Z\subseteq V(G)$ : $\mid Z \mid \leq \mid \cup_{z\in Z}\; I(z) \mid $ Can someone ...
1
vote
1answer
35 views

Algorithmic Graph Theory - perfect matching in bipartite graph when det(A) is not 0

While learning about graphs, I came across theorem that I don't quite understand, and can't find a proof. If G is bipartite, and $\det(A) \neq 0,$ then G has a perfect matching. (Given that matrix ...
3
votes
3answers
199 views

Prove that the complete bipartite graph $K_{3,s}$ has $s^23^{s-1}$ spanning trees for $s\geq2$

I am wondering about a more combinatorial proof for this question as I have only seen the proof using Kirchoff theorem? Any help would be much appreciated!
1
vote
1answer
43 views

Bipartite allocation with minimum cost

Given two vertex sets $V_1$ and $V_2$. The vertices in $V_2$ have a limitation on the maximum degree of each vertex being $K$. I need to find an allocation algorithm such that every pair of vertices ...
1
vote
1answer
63 views

Does Kőnig's theorem hold for infinite bipartite graphs?

Kőnig's theorem states that in a bipartite graph the size of the maximal matching equals the size of the minimal vertex cover. I learned it as an equivalence to Hall's theorem and we proved it using ...
1
vote
2answers
116 views

Frustration of a weighted bipartite graph

Given a bipartite graph with $|V_1|=n$ and $|V_2|=m$, we can assign each vertex with value $-1$ or $1$, and we can assign each edge with any real value. Define an energy function as such: $$ V = \...
0
votes
0answers
20 views

Proving that the set of maximal-degree vertices of a Graph result in a matching for all vertices [duplicate]

A question on my Graph Theory Homework is as follows, and I'm unsure about how to start solving it. Any tips would be greatly appreciated. Consider a bipartite graph. If M ⊂ V be the vertices of ...
0
votes
1answer
37 views

Smallest possible girth of an arbitrary bipartite graph

I am working on a problem set for school right now and I have the following question: Let $G$ be an arbitrary bipartite graph. What is the smallest possible girth of $G$? Explain I have been ...
0
votes
0answers
35 views

Proof: A graph that does not contain any closed walks with odd length is bipartite.

I came across this proof in the book Mathematics for CSE by E.Lehman and F.T. Leighton(2010 version). They prove that a graph with no walks of odd length is bipartite. Here is the proof: 4 IMPLIES ...
0
votes
1answer
14 views

What can we say about graph G?

Let G be a bipartite graph that does not have a perfect matching, but if we add any new edge to G, then the new graph G+ is no longer bipartite, but has a perfect matching. What can G be? I found one ...
0
votes
0answers
31 views

Choice of augmenting path in the Augmenting Path Algorithm + Proof of correctness

I'm watching this video of an example of the Augmenting Path Algorithm. https://youtu.be/C9c8zEZXboA?t=240 For convenience, I name the vertices of X, from left to right, $x_1, x_2, x_3, x_4, x_5, x_6$...
1
vote
1answer
63 views

Selecting elements from overlapping sets in any order without repetition

(there are examples below in this question, which probably explain it all better) Consider a finite set $R = \{1, 2, ..., N\}$ and a tuple of sets $Q = (S_1, S_2, ..., S_M)$, which are possibly non-...
1
vote
1answer
41 views

Is the converse true?

Let $G$ be a connected bipartite graph with partite sets $X$ and $Y$ such that cardinality of $X$ equals to cardinality of $Y$ $\geq$ 2. If every two vertices of $X$ have distinct degrees in $G$ then ...
3
votes
2answers
79 views

Perfect matchings in bipartite graphs.

Question: $G$ is a bipartite graph where $|X| = |Y| = n$ and $|E| \geq n^2 - \frac{2n}{3} + 3$. $X$ and $Y$ are the set of vertices and $E$ is the set of edges. Prove that $G$ has a perfect ...
0
votes
1answer
53 views

If $G$ is a bipartite Euler and Hamiltonian graph, prove that complement of $G$, $\bar G$ is not Eulers.

I would like to know if my proof of the statement in the title is correct. So, I started like this: As $G$ is a bipartite graph, it has two sets $X$ and $Y$. Using the condition $G$ is Hamiltonian, ...
1
vote
1answer
60 views

Identifying a Maximum matching and a minimum cover for a specific bipartite graph

I have been given the following matching: $$ M =\{ \{a,3\}, \{b,1\},\{d,4\},\{f,5\}, \{g,6\},\{h,7\},\{i,9\} \}$$ in the bipartite graph: The matching looks like: I applied the augmented path ...
0
votes
1answer
50 views

Graph Theory closest to be bipartite

I have two graphs graphs I know it isn't bipartite, but I need to calculate which one is closest to being bipartite, it is related with bipartivity in network. To define a measure of network ...
1
vote
2answers
44 views

Minimum cardinal number of a set contains all the paths of a complete bi-partite graph

What is the minimum cardinal number of a set contains all the paths of a complete bi-partite graph: K(7,10), where every edge of the graph must be in one (and only one) of these paths. how can I ...
0
votes
2answers
87 views

A bipartite graph

We know that all trees are bipartite. Suppose the vertices of the tree when converting to a bipartite graph belong to the two sets A and B. It is not important that the number of vertices in the two ...
2
votes
1answer
47 views

Prove $D-A$ is similar to $D+A$ iff the graph is connected and bipartite

If $A$ is the adjacency matrix for the Graph $G$ and $D$ is the diagonal matrix of degrees, $D-A$ is the laplacian of the graph and $D+A$ is sometimes called the signless laplacian. I want to prove ...
0
votes
0answers
22 views

Maximum weight matching with repeated nodes

We are given two sets of nodes $A$ and $B$ forming a graph where each element $x \in A$ can be connected with an element $y \in B$ with different possible weights. The graph can be explained in two ...
0
votes
1answer
26 views

Find an edge subset such that the graph is bipartite.

Let $G$ be a undirected Graph. Find the minimal subset of edges $F$ such that $G$ without $F$ is bipartit. Prove that this is possible in linear time, meaning Number of Nodes + Number of Edges. I ...
1
vote
1answer
45 views

Modelling of a flow network with a positional constraint

While I do realise pasting an exercise question in here is not exactly perfect form, I am desperate and I wil try anyway. So here it goes: Consider a set of n mobile computing clients in a town with ...
0
votes
1answer
62 views

Weaker version of Hall's condition

In chapter 1 of Lubotzky's "Discrete Groups, Expanding Graphs and Invariant Measures", remark 1.1.2, one definition of expanders is the following: if $n, k \in \mathbb{N}$ and $c \in \mathbb{R}_{> ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
41 views

Alternative words for “parts” of a bi-partite graph

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 ...
0
votes
1answer
124 views

Max flow min cut in matching reduced to max flow

I can not find the max flow, min cut in this graph where all edges have capacity 1. The graph: 1 The max flow in this graph from s to t is 2? But it is impossible to separate s and t without cutting ...