Questions tagged [bipartite-graphs]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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!
0
votes
1answer
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$
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
66 views

Maximum number of edges of a bipartite connected graph with vertex classes of size $n$ and with no perfect matching

At most how many edges can a connected bipartite graph with $n$ vertices in each class can have so that there is no perfect matching? If we omit the connectedness condition, then the maximum is $n(n-1)...
1
vote
1answer
27 views

In a bipartite graph the absolute value of any eigenvalue is less than the square root of number of edges.

Let $G$ be a bipartite graph with $e$ edges. How do we show that the absolute value of any eigenvalue $\lambda$ of $G$ (i.e., the eigenvalue of the adjacency matrix of $G$) is less than or equal to $\...
1
vote
1answer
33 views

Matching in bipartite graph $|M|\geq \frac {n}{\Delta (G)}$.

Given a bipartite graph, with n edges. Prove that there exist matching M such that $|M|\geq \frac {n}{\Delta (G)}$. Can someone check my solution. Can this be proved by induction, over $\Delta$. For, $...
1
vote
0answers
37 views

Partitioning crown graphs into girth 6 diameter 3 subgraphs / packing of graphs representing finite projective planes

I came up with this original conjecture several years ago, and the formal wording below about a year afterwards. My conjecture: For all primes $P$, there exists a $P$-color edge coloring of the $2(P^...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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?
0
votes
0answers
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 ...
2
votes
1answer
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, ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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.
2
votes
0answers
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 ...
4
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
6
votes
0answers
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$,...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
3
votes
0answers
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 ...
1
vote
0answers
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|$...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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,...
0
votes
0answers
48 views

Number of marriage arrangements if Hall’s condition satisfied [duplicate]

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

Applying Hall's Theorem to a tripartite graph

Hall's theorem works for bipartite graphs and shows there is a complete matching if Hall's condition holds. If I have a tripartite graph $(X,Y,Z,E)$ and Hall's condition holds from $X$ to $Y$ , from $...
1
vote
0answers
85 views

Number of possible marriage arrangements if Marriage Condition is satisfied

Suppose I have a set of $n$ boys and each subset of $1\leqslant k \leqslant n$ boys knows at least $k$ girls then this means that the set of boys $B$ satisfies the marriage condition. I am doing an ...
1
vote
1answer
52 views

Hall's marriage theorem with infinitely many people

I fully understand Hall's marriage theorem, if I have $n$ boys and $m$ girls and if every subset of $k$ boys knows at least $k$ girls then there exists a matching between the boys and girls. What ...
0
votes
1answer
47 views

Minimal bipartite graph

If I have a bipartite graph between two sets B and G of size $N$ such that every subset $A$ of vertices in B is connected to at least $|A|$ vertices in G. If I delete all the redundant edges (those ...

1
2 3 4 5
10