Skip to main content

Questions tagged [bipartite-graphs]

For questions about graphs for which the set of vertices can be divided into two disjoint subsets such that no edge of the graph joins two vertices from same subset.

Filter by
Sorted by
Tagged with
1 vote
0 answers
38 views

Is colour smoothness equivalent to finding a cover via disjoint cycles?

Let $G$ be a finite bipartite graph, with colouring function $c \colon V(G) \to \{-1, 1\}$. I want to consider the problem of finding vertex-disjoint cycles whose union spans $G$. We have the ...
gmz's user avatar
  • 117
0 votes
0 answers
31 views

Value range of dual variables in Jonker-Volgenant algorithm for solving linear assignment problem

In A shortest augmenting path algorithm for dense and sparse linear assignment problems an algorithm for the Linear Assignment Problem is given, with a $O(N^3)$ time complexity (where $N$ is the "...
Oersted's user avatar
  • 161
1 vote
1 answer
43 views

Zarankiewicz’s conjecture

The Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph. A few years later, Zarankiewicz published a formula that provided a solution to ...
Yeipi's user avatar
  • 525
2 votes
1 answer
58 views

Number of edges in planar bipartite graph.

Suppose G=(V,E) is a planar bipartite graph such that $V_1$ and $V_2$ are the partite sets. Suppose for all $a \in V_1$, $deg(a)\le p$ and for all $b \in V_2$, $deg(b)\le q$. If $|V_1|=x$ and $|V_2|=y$...
Abhimanyoo Karve's user avatar
0 votes
1 answer
33 views

I would like to prove the following: If $C$ is an odd cycle in $G$, then $G-V(C)$ is a bipartite graph.

Let $G$ be a graph in which for every pair of odd cycles $C_1$ and $C_2$ in $G$, it holds that $V(C_1) \cap V(C_2)$ is not an empty set. I would like to prove the following: If $C$ is an odd cycle in $...
lolip123's user avatar
  • 101
1 vote
1 answer
43 views

A matching problem with $N$ men, $N$ women and $N$ houses [closed]

Consider a matching problem with $N$ men, $N$ women and $N$ houses where each man has to be paired with exactly $1$ woman and then each couple has to be allotted to $1$ house. Now let's consider all $...
vervenumen's user avatar
0 votes
1 answer
48 views

$G(n,1/2)$ has a bipartite subgraph with at least $n^2/8+Cn^{3/2}$ edges

I want to show that with probability converging to $1$, $G(n,1/2)$ has a bipartite subgraph with at least $n^2/8+Cn^{3/2}$ edges for some positive constant $C$. The hint for this is to use a greedy ...
Anon's user avatar
  • 527
3 votes
1 answer
33 views

Hamiltonian graph on a $8\times 8$ chessboard with upper left corner and bottom right corner square removed

Suppose we are given the setup in the title. Two squares are adjacent if and only if they share a common edge. I want to find out whether the obtained graph considering squares as nodes would be ...
Sj2704's user avatar
  • 79
0 votes
0 answers
29 views

Prove that for complete biclique Ki,j that ∆(Ki,j) = χ′(Ki,j).

I am trying to prove it by contradiction. Proof: "Assume that ∆(Ki,j) != χ′(Ki,j) for a complete biclique (Ki,j). If ∆(Ki,j) > χ′(Ki,j), it implies that the minimum number of colors needed to ...
Banon Bhuiyan's user avatar
1 vote
1 answer
29 views

Terminology for a "semi-bipartite" graph strucure (graph theory)

Let $G$ be a finite graph whose vertices can be divided into two disjoint sets $U$ and $V$ such that a vertex in $V$ can be connected to any vertex in $G$, but a vertex in $U$ can be connected only to ...
DYZ's user avatar
  • 111
1 vote
1 answer
33 views

Correct Counting of Independent Sets in a Complete Bipartite Graph $(K_{n, m})$

I'm diving into graph theory and am currently focused on understanding independent sets within complete bipartite graphs. Specifically, I've been pondering over how to accurately count the total ...
neo's user avatar
  • 109
0 votes
1 answer
62 views

Graph $ G $ is bipartite if and only if the eigenvalues of graph $ G $ occur in pairs $ \lambda, \lambda' $ such that $ \lambda' = -\lambda $.

Let $ G = (V, E) $ be an arbitrary graph, and let $ v_i, v_j $ be any vertices of graph $ G $. Let $ A $ be the adjacency matrix of graph $ G $. Prove the following statements: (a) The number of $ v_i,...
ukm2030's user avatar
  • 51
1 vote
1 answer
40 views

How many subgraphs of $K_{9,9}$ are isomorphs of $C_6$?

I approached this problem the following (apparently incorrect) way: In $K_{9,9}$, there are 18 vertices, so 18 choices for a starting point. From there, since the graph is bipartite, whichever "...
JBatswani's user avatar
2 votes
1 answer
125 views

Lower bound on the number of complete bipartite graphs to partition the edge set of $G$

Let $bp(G)$ be the number of complete bipartite graphs needed to partition the edge set of G. This means, $ \forall e \in E(G) $, e is in exactly 1 complete bipartite graph. Now, how to prove bp(G) $ \...
jim's user avatar
  • 85
10 votes
1 answer
178 views

(Hall's Theorem) Existence of two subfamilies of sets containing the same elements

I came across the following claim in a textbook on combinatorics [1]. Claim (Lindström, Tverberg): Let $A_1, . . . , A_m \subseteq [n]$ be non-empty with $m > n$. There are non-empty, disjoint $I, ...
xyz's user avatar
  • 103
-1 votes
1 answer
40 views

Counting crossings of a particular complete bipartite graph [closed]

This type of complete bipartite graph has two vertex sets $(V,U)$ where $V$ has points $v_n$ along a straight line parallel to the set of points $u_m$. How should I go about finding a general formula ...
Joël's user avatar
  • 9
2 votes
0 answers
43 views

Bipartite intersection graph

Recently, I'm trying to learn geodesic currents on free groups through a paper by Kapovich and Lustig. Let $\langle, \rangle: \overline{CV}(F_N)\times Curr(F_N)\to\mathbb{R}$ be the intersection form ...
quuuuuin's user avatar
  • 637
1 vote
1 answer
30 views

A graph is bipartite if and only if for $vw\in É$, for all $a\in V$, the shortest path from $a$ to $v$ is not equal with from $a$ to $w$

I need to prove that a simple graph $G=(V,E)$ is bipartite if and only if for $vw\in E$, for all $a\in V$, the length of the shortest path from $a$ to $v$ is not equal with that between $a$ and $w$. ...
toki's user avatar
  • 95
1 vote
1 answer
95 views

Does the graph have a Hamiltonian circuit or a Hamiltonian path?

Certain necessary conditions for a Hamiltonian circuit such as the graph being 2-connected, having zero pendants are met. Dirac's and Ore's theorem provide sufficient conditions, which are not ...
0x13's user avatar
  • 415
2 votes
0 answers
89 views

Finding a perfect matching that include $e_{1}$ and exclude $e_{2}$ in a connected bipartite graph

Let $G$ be a $k$-regular bipartite graph with $k\ge3$, and $e_{1},e_{2}$ be edges of $G$. Show that if $G-\{e_{1},e_{2}\}$ is connected, then there exist a perfect matching in $G$ that includes $e_{1}$...
Kevin's user avatar
  • 734
3 votes
0 answers
58 views

Variance of a sample from a bipartite graph

Consider a bipartite graph for which the two vertex sets have the same size, denoted $M=|V_1|=|V_2|$. Let $d$ denote the maximum degree of vertices in $V_1\cup V_2$. Assume that $M$ is large and ...
Kris Tapp's user avatar
1 vote
1 answer
45 views

Find bipartite graph with properties [closed]

Problem: Find a bipartite graph such that a) Each part of the graph has 15 vertices b) Each vertex has a degree of at least 7 c) There is no matching of size 15. How can I construct such graph?
popcorn's user avatar
  • 311
2 votes
1 answer
51 views

graph bipartiteness is not expressible in first oder logic

Definitions: a) Let $\sigma$ be a vocabulary. A property P is a set of $\sigma$-structures, P $\subset$ STRUCT($\sigma$). b) Let $\phi$ be an FO sentence. Mod(φ) := {$\alpha$ : $\alpha$ ⊧ $\phi$} ($\...
StudentSeekingHelp's user avatar
5 votes
2 answers
278 views

Proof of statement regarding bipartite graphs

I'm trying to prove the following proposition as an exercise, and I'm stuck at some point. Let $G$ be a graph that doesn't contain $C_3$ or $P_4$ as an induced subgraph. Then $G$ is bipartite. My ...
VlakecTomaz's user avatar
3 votes
1 answer
88 views

Bipartite graphs coloring

I was asked about an elementary (math olympiad) problem regarding members and committees, which can be formulated as the following graph-theoretic problem. Given a bipartite graph $(V_1\cup V_2, E)$, ...
maomao's user avatar
  • 1,219
1 vote
1 answer
108 views

Prove that G-x-y has a perfect matching iff x and y are on opposite sides where G is Hamiltonian

Question: Suppose G is Hamiltonian bipartite graph with $ x , y \in V(G) $. Prove that $G-x-y$ has a perfect matching if and only if $x$ and $y$ are on the opposite sides of the graph. Proof: $\...
i_hate_pure_math's user avatar
1 vote
1 answer
101 views

Vertices of Matchings in bipartite Graph are Matroid

Let $G=(V,E)$ be a bipartite graph with $V=A \cup B$ (disjoint) and $\mathcal{F}=\{V(N) \cap B\ |\ N\ is \ a\ matching\ in\ G\}$ . Now I have to prove that $(B,\mathcal{F})$ is a matroid. The first ...
Norn0556's user avatar
2 votes
0 answers
82 views

Diameters of random bipartite graphs [closed]

Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
Zijian Wang's user avatar
2 votes
1 answer
84 views

G a k-connected bipartite graph with bipartition $(A, B)$ such that $|A|$, $|B| \geq 2k$. Show that $G$ contains a matching of size $2k$.

Let $k \geq 1$ be an integer, and let G be a k-connected bipartite graph with bipartition $(A, B)$ such that $|A|$, $|B| \geq 2k$. Show that $G$ contains a matching of size $2k$. I have managed to ...
The Math Hermit's user avatar
0 votes
1 answer
45 views

Connectivity of bipartite graph

We consider $G$ to be a bipartite graph that is $(d \geq 1)$-regular and has at most $4d-1$ vertices. We wish to show that $G$ must be connected. My thinking was to prove by contradiction. So $G$ has ...
Jeff's user avatar
  • 401
0 votes
1 answer
42 views

Find all the nonisomorphic complete bipartite graphs $G=(V,E)$ where $ |V|=6$

I am confused by this question. The answer guide says that there are 3 graphs. i) $K_{1,5}$ ii) $K_{2,4}$ iii) $K_{3,3}$. I don't see how I can draw them to be non isomorphic. This question is from ...
LordAgame's user avatar
1 vote
0 answers
78 views

Let $G = (V, E)$ be a simple graph. $G$ is bipartite if and only if every cycle has even length

I'm trying to prove: Let $G = (V, E)$ be a simple graph. G is bipartite if and only if every cycle has even length. For the left-to-right implication, I did the following: suppose G is bipartite, ...
J P's user avatar
  • 869
0 votes
2 answers
71 views

Monochromatic $4$-Cycle in Bipartite Complete Graph [closed]

Given a complete bipartite graph on $n$, $n$ vertices (call this $K_{n,n}$), we colour all its edges using two colours, red and blue. What is the least value of $n$ such that for any colouring of the ...
Nishkarsh's user avatar
1 vote
1 answer
27 views

Thickness of non-complete bipartite graph [closed]

Is there any analytical result or algorithm on computing the thickness of a non-complete bipartite graph? I really tried to find anything but didn't succeed.
Unknown's user avatar
  • 19
1 vote
0 answers
66 views

How to prove a $d$-regular bipartite graph is $d$-edge colourable by using Konig theorem

Problem: Prove that a $d$-regular bipartite graph is $d$-edge colourable using Konig-Egervary theorem If the the graph $G$ is bipartite then the size of max-matching equals to the size of min-vertex-...
ohana's user avatar
  • 873
4 votes
1 answer
218 views

Number of bipartite graphs given two sets

I'm currently studying for an exam related to graphs, reason why I have been asking several question of this topic. In this case, I am confused about the definition of bipartite graph, at least up to ...
Emmy N.'s user avatar
  • 1,361
0 votes
1 answer
329 views

the complement of bipartite graph is perfect

Let G be a bipartite graph, and prove that the complement of G is a perfect graph. the complement of bipartite graph is a graph where the 2 groups of vertices of the original graph turns into a clique,...
Kevinlove's user avatar
  • 171
3 votes
0 answers
119 views

Largest number of disjoint subsets of certain cardinality in bipartite graph such that every vertex is matched

Given a bipartite graph $G=(V,E)$, where $V$ is partitioned into $A$ and $B$, how can I design an algorithm that runs in polynomial time, such that given a positive integer $n\in\mathbb{N}$, the ...
Vista0711's user avatar
0 votes
1 answer
180 views

Why is a bipartite graph in which every vertex has degree exactly $2$ is simply a cycle?

I am trying to intuitively understand why a bipartite graph in which every vertex has degree exactly $2$ is simply a cycle. So far, I have tried to intuitively justify this by saying that an Eulerian ...
Princess Mia's user avatar
  • 2,533
0 votes
1 answer
27 views

Moving edges of bipartite graph to the leftmost?

Given a bipartite graph $G$ with two sides $A=\{a_1,\dots, a_n\}$ and $B=\{b_1,\dots, b_n\}$. I define a ``pressing" operation $f_{a_i,a_j}(G)=G'$ for $i<j$: $G'[A\cup B\setminus\{a_i,a_j\}]=G[...
Connor's user avatar
  • 2,085
1 vote
0 answers
73 views

Prove bipartite graph with maximum degree d is a subgraph of a d regular bipartite graph

How can I show that every bipartite graph of maximum degree d is a subgraph of some d-regular bipartite graph. If something I'm saying could be better mathematically phrased, please let me know. Let'...
shrizzy's user avatar
  • 784
1 vote
2 answers
66 views

Finding the set that violates Hall’s condition in a bipartite graph.

If I have a bipartite graph for which it is given that there does not exist any complete matching. This implies that Hall’s condition is not satisfied for this graph. So, there must be atleast one set ...
ARROW's user avatar
  • 751
1 vote
1 answer
35 views

Hamiltonicity of bipartite graphs maximum degree $3$, where $X$ or $Y$ is a clique

I'm quite new to graph theory and NP-complete proofs. I stumbled across NP-completeness on hamiltonicity of bipartite graphs with maximum degree $3$ and was wondering whether the same applies to ...
Melo12's user avatar
  • 13
3 votes
1 answer
127 views

Bondy, Murty Graph Theory exercise 16.2.12 (by Noga Alon)

Let $G = (U\sqcup V, E)$ be a bipartite graph in which each vertex of $U$ is of odd degree. Suppose that any two vertices of $U$ have an even number of common neighbours. Show that $G$ has a matching ...
Robert's user avatar
  • 581
1 vote
1 answer
65 views

Variant of vertex cover in bipartite graphs [closed]

I have this problem, and I am not sure whether it is known. Given a bipartite graph $G(U, V, E)$. Define two sets $V_{e}, V_{o} \subseteq V$ such that $V_{e}$ and $V_{o}$ are disjoint. Now, define ...
EMM712's user avatar
  • 19
2 votes
1 answer
46 views

How can we use a cartesian product in the definition for bipartite graph when its elements are tuples and edges can be sets?

I have learnt that in a bipartite graph, we can partition vertices into 2 sets $V_1$ and $V_2$, and $E \subseteq V_1 \times V_2$. However, the cartesian product is a set of tuples, and edges (in an ...
Princess Mia's user avatar
  • 2,533
2 votes
4 answers
251 views

Prove that all graphs with Degree Sequence $(2,2,2,2,2,2,2)$ have an odd cycle.

I've been asked to prove that a graph with Degree Sequence $(2,2,2,2,2,2,2)$ [2-regular, 7 vertices] cannot be bipartite. I know that bipartite graphs cannot have any cycles of odd length. I'm fairly ...
Robert Kim's user avatar
1 vote
0 answers
175 views

No eigenvalue of a graph is larger than the maximum degree

This is exercise 1.1.24 in "Graph Theory" by Bondy and Murty: $(a)$ No eigenvalue of a Graph $G$ has absolute value greater than $\Delta$ $(b)$ If $G$ is a connected graph and $\Delta$ is ...
leon.fuchsler's user avatar
0 votes
0 answers
46 views

Bipartite Matching Proof

Let $G=(V,E)$ be a bipartite graph $|L| = |R| = n$ Given the graph G has no perfect matching how can i prove that G has $L_1$ $\subset $ L and $R_1 \subset R $ such that $|L_1| + |R_1| = n+1$ and $...
Ofir Avisar's user avatar
1 vote
0 answers
42 views

Minimal slices for dividing $m$ pizzas to $n$ people is $m+n-\gcd(m,n)$

The following problem is taken from Graph Theory by Adrian Bondy, U.S.R. Murty, crediting H. Bass. m identical pizzas are to be shared equally amongst n students. The pizzas are not necessarily ...
Robert's user avatar
  • 581

1
2 3 4 5
15