# Questions tagged [bipartite-graphs]

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

481 questions
Filter by
Sorted by
Tagged with
19 views

### Given a perfect fractional matching, does there exist a perfect matching with heavy edges?

Let $G = (X\cup Y, E)$ be a bipartite graph in which $|X|=|Y|=n$. Suppose $G$ admits a perfect fractional matching, that is - a function assigning a non-negative weight to each edge, such that the sum ...
19 views

### Matchings in bipartite graph

I was given the following statement: Be $G=(X \cup Y, E)$ a bipartite graph connected with $|X|=|Y|=4$ $|E|=7$ , all maximal matching in G is maximum. I must say if it is true or false and justify. By ...
30 views

### connected bipartite graph exists

Does a connected bipartite graph $G=(X \cup Y; E)$ such that $|X|=4$, $|Y|=3$, $|E|=5$ exist? Is there a way to know? Thanks!
23 views

### Isomorphic graphs derived from $K_{10,10}$

How many subgraphs of $K_{10,10}$ exist that are isomorphic to the graph $G$ on the picture? I can think of $P(10,10)$ but I don't think that all of these cases are isomorphic with $G$
32 views

### Graph theory: Questions about Hamiltonian cycles.

Prove that if graph $G$ has $n \geq 2$ vertices such that the sum of the degrees of $2$ different vertices is at least $n- 2$, so there are $2$ different simple paths ('foreign' to one another) such ...
57 views

### Under what condition is a complete bipartite graph $K_{m,n}$ a regular graph

This is a quick question and I know all about these graphs what I am supposed to know. But I am unable to explain myself in words. Like I know for regular graph the vertex must have same degree and ...
32 views

### Perfect Matching on Bipartite Graph

So I was trying to solve this problem Let $H$ be a bipartite graph with bipartition $A,B$ such that $|A| = |B| = k$. Prove that the graph contains a perfect matching when every vertex has degree of ...
51 views

### Is there something incorrect in this question?

Let G be a bipartite graph with two Groups A, B. Given: |A| =2, |B|=n and that there are edges that connect every single node in A with every node in B. Let T be a spanning tree of G, Prove that There ...
43 views

### Which generalization of bipartite graphs is stronger?

Here are some ways to generalize the notion of a bipartite graph to hypergraphs: A hypergraph is called 2-colorable if its vertices can be 2-colored such that each hyperedge of size at least 2 ...
66 views

33 views

31 views

### On the hard direction proof of Hall's theorem for bipartite graphs

The hard-direction proof of Hall's Theorem in bipartite graphs is given as follows (Source Wikipedia): We assume that there is no $X$-saturating matching and prove that Hall's condition is ...
14 views

### Is there a name for this representation of a bipartite graph?

In dealing with bipartite graphs, I usually use a compact representation I came up with myself, which I find handy. If the graph has M nodes on the left and N nodes on the right, I can represent it ...
78 views

### Graph Theoretical Game: Repeatedly deleting a $C^k$ from a $K^n$

Having solved the following exercise, I wonder what happens if you change it slightly. Let $n \geq 4$. A bored mathematician plays the following game: She starts with a complete graph $K^n$. In ...
42 views

### Show that $K_{r, s}$ is planar if and only if $\min$ {r, s} ≤ 2.

So I've done some draws and this is true, but How can I argument to prove that, by the maximum number of edges in $K$ ? Or by $d(v)$ Any help?
18 views

### Bipartite graph degree

We have two sets of vertices $|V_1|$ and $|V_2|$ in a bipartite graph Now the total number of edges in the bipartite graph can be calculated as $E=|V_1|+|V_2|$ $m=|E|$ where $r=|V_2|$ is it ...
55 views

### Assume the bipartition of $G$ is $V=A\uplus B$. Prove that $|A|=|B|$ [closed]

Let $G$ be a bipartite graph whose every vertex has the same degree $d$. Assume that the bipartition of $G$ is $V=A\uplus B$. Prove that $|A|=|B|$. I'm not great at figuring out how to start proofs, ...
32 views

### Determining the most possible number of winners in a raffle

Every year we do a raffle at my job with prizes that were donated by local businesses. Everyone can select 5 prizes they'd like to win from a total of x number of prizes. After that a winner is ...
21 views

### Bipartite Graph Community detection

The main idea is I want to cluster a bipartite network based on total number of shared nodes. Here is an example A bipartite network A bipartite network clustered on the criteria that the rectangle ...
25 views

### Dirac's theroem for bipartite graphs

The theorem of Dirac that any graph $G$ on $n\geq 3$ vertices with minimum degree $\delta(G)≥n/2$ contains a Hamilton cycle is one of the classical results of graph theory. Is there are analogous ...
27 views

### Entries of a matrix represented as a graph

I have to go through this paper, where I encountered this definition: The pattern of a matrix A is a bipartite graph with a node for each row and each column and an edge connecting row node i to ...
30 views

### Maximal Matching in Bipartite Graph with Degrees Given

I'm quite stuck on how to go about showing the second part of the following question: Assume $G(V,E)$ is a bipartite graph with bipartition $V = P\cup Q$ and every vertex in $P$ has degree $a$, and ...
29 views

### Quantifying non-bipartiteness

Suppose I have a graph that is bipartite, except for one edge. That is, if this one edge were deleted, the graph would be bipartite. This graph is 'almost' or 'very nearly' bipartite. A complete ...
16 views

### Is the Hungarian assignment algorithm, Wikipedia version, correct?

The Wikipedia description of the Hungarian algorithm states: Step 3 All zeros in the matrix must be covered by marking as few rows and/or columns as possible. The following procedure is one ...
21 views

### Can a bipartite graph not contain a Hamiltonian cycle?

Statement: any bipartite graph contains a Hamiltonian cycle. My answer: No. A bipartite graph which have an odd number of vertices cannot contain a Hamiltonian cycle, since each simple cycle in a ...
12 views

### Looping through preference list

I am trying to understand the looping through preference list in the context of Stable Matching. I am reading the following paper available at: MPCircuits: Optimized Circuit Generation for Secure ...
46 views

### eigenvalues of k-regular bipartite graph adjacency matrix.

I need some help with this proof: Let G be a k-regular graph. prove that: a) If G is bipartite then -k is an eigenvalue of G's adjacency matrix. b) If -k is an eigenvalue of G's adjacency matrix then ...
43 views

### Incidence matrix and biadjacency matrix of bipartite graph

For a simple bipartite graph, the adjacency matrix can be written as $$A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}$$ where $B$ is called biadjacency matrix. Is there a relation ...
11 views

### Degree distribution in bipartite graph.

Why is it important to maintain the degree distributions of both sides in a bipartite graph especially in broadtail networks.
24 views

### Almost Regular Subgraph of Sparse Graph

Definitions: A spanning subgraph of a graph $G$ is a subgraph of $G$ including all its vertices. An almost $r$-regular graph is a graph whose degrees are either $r$ or $r-1$. Question: Suppose we ...
62 views

### Reducing the Degrees of a Graph where All Degrees are Quite Concentrated

Suppose the degrees of all vertices in a graph $G$ (say, a bipartite graph) are all in a very concentrated range $[d(1 - o(1)), d(1 + o(1))]$, with $d$ an arbitrarily large constant. Here $o(1)$ is a ...
52 views

### If all 2-faces of a polytope are $2n$-gons, is the edge-graph bipartite?

I wonder if I can see easily whether the edge graph of a (convex) polytope $P\subset\Bbb R^d$ is bipartite or not. A graph is bipartite if and only if all its cycles have even length. I thought about ...
79 views

### Perfect matching in a random bipartite graph with edge probability 1/2

I am trying to prove that, when given a bipartite graph $G=(X \cup Y, E)$ with $|X|=|Y|=n$ and edge probability $\frac{1}{2}$, as $n\rightarrow \infty$ the probability of the graph having a perfect ...
42 views

### A connected k-regular bipartite graph is k-connected.

I've seen the similar question "A connected k-regular bipartite graph is 2-connected" answered: A connected k-regular bipartite graph is 2-connected. Prove that every connected k-regular bipartite ...
33 views

### construct graph using max flow algorithm

Given n pair of integer (di, dj), e.g. (0, 2), (1, 1), (1, 0), (1, 0)... Construct a directed graph G = ({1...n}, E) such that in-degree of vertex 1 is di and out-degree is dj. Is it possible to ...
63 views

### Extending a theorem from bipartite graphs to tripartite hypergraphs

Here is a useful theorem on bipartite graphs. Theorem. Let $G = (X\cup Y,E)$ be a bipartite graph with $n$ vertices in each side and positive weights on the edges. If for each vertex $v \in X\cup Y$,...
18 views

### Augmenting Path and Matching

I am trying to get the maximum matching in a bipartite graph. I'm trying to apply Hopcroft–Karp algorithm (https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm). I have little confusion over ...
95 views

### Counting the number of bipartite graph with 4 vertices.

I know this may sound like a simple question, as you can count all the bipartite graph in this case. Let $U$ and $V$ be the parts of the bipartite graph. If you put 2 vertices in $U$ and 2 vertices in ...
40 views

### Bipartite matching with degree and “budget” constraint

Consider a bipartite graph of vertices of people $P_1,P_2,\dots,P_p$ with edges connected to vertices of tasks tasks $T_1,T_2,\dots,T_t$. An edge from $P_i$ to $T_j$ means that the person $P_i$ can do ...
23 views

### Formula for the size of the union of neighbourhoods in a graph

If $A,B \subseteq X$ and $|N(A)|=|A|$ and $|N(B)|=|B|$ in a finite bipartite graph $G$ with bipartition $X\cup Y$ then is it true that if Hall's condition holds on $X$ that: $|N(A \cup B)|=|A \cup B|$...
17 views

### graph theory neighbourhoods

Can someone please help me show why if $A,B \subseteq X$ and $|N(A)|=|A|$ and $|N(B)|=|B|$ in a finite bipartite graph $G$ with bipartition $X\cup Y$ then $|N(A \cup B)|=|A \cup B|$. Note: Hall's ...
65 views

### Infinite hall's theorem

If $G=(U,V,E)$ is an Infinite bipartite then Hall's condition is a necessary condition for there to be a matching saturating $U$. However this condition is not sufficient in this Infinite case. If ...
32 views

### People on the train, prove 3 people know each other or don't know each other. [duplicate]

There are 6 people on the train. Prove that there are 3 people among them that know each other or don't know each other. My first instinct is that it might have to do something with a bipartite graph,...
Show that if a set of $n$ boys satisfies Hall’s marriage condition and each individual boy knows at least $t>n$ girls then the number of possible marriage arrangements between boys and girls is ...