# 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.

599 questions
Filter by
Sorted by
Tagged with
0answers
13 views

### Let G be a connected graph with at least one cycle. Proof that G is biparthite when no cycle is odd [duplicate]

So i have this task i am a little bit lost how to approach this problem. Could anyone guide me trough it? Let G be a connected graph with at least one cycle. Proof that G is bipartite when no cycle is ...
1answer
22 views

### let $G$=$(V,E)$ be a connected, d- regular bigraph. Prove that for any v, $G'$ = $G$ \ ${v}$ is connected.

Let $G=(V,E)$ be a connected, $d$-regular bigraph. Prove that for any $v\in V$, $G' = G\setminus\{v\}$ is connected. $G$ is a bigraph, so $V = A\cup B$. $G$ is also $d$-regular, so $|A| = |B|$. I ...
0answers
25 views

### Mapping in graph and bipartite graphs

Let $G$ be a bipartite graph. In order to find a match in the $G$ diagram so that there are no unpaired elements in the set $A$, a necessary and sufficient condition is $|A-N(T)|\leq|B-T|$ that is ...
0answers
35 views

### Is there a regular bipartite graph where the minimum cuts are trivial?

My question is: Given integers $r$ and $k$, is there an $r$-regular bipartite graph $G = L \cup R$ with $|L| = |R| = k$, which is $r$-edge connected, and such that every minimum cut is trivial? I can ...
2answers
42 views

### Is $K_1$ bipartite?

I'm thinking that it could be trivially bipartite since it only has one vertex and no edges but I am still a little bit unsure about it being trivially bipartite.
0answers
11 views

### generate all connected bipartite graphs with given bipartition using nauty

Given a number of vertices in partition A and partition B, I want to generate all connected bipartite graphs. I have found the nauty software package and can generate all graphs of a specified class ...
2answers
24 views

### Does a bipartite graph without perfect matching exist?

I know that not all bipartite graphs have perfect matching, but I am having trouble coming up with an example (I'm a visual learner). Can someone give me a visual example of a bi[artite graph without ...
0answers
36 views

### Bipartite Graph No Matching [closed]

Can someone provide me, a resource that could explain the answer to this problem (see above)? What is the name of the method they use? I'm looking to a resource that could explain the answer since the ...
0answers
19 views

1answer
23 views

### Graph Theory, Bipartite Graph Formula [closed]

Let Graph G = (A, B, E) be a bipartite graph. |A| = a, each vertex in A has degree x; each vertex in B has degree y. Whats a formula for the number of vertices in B ?
1answer
43 views

### How to show this bipartite graph has a matching saturating X?

Let $G$ a bipartite graph with partitions $X$, $Y$ such that all degrees in $X$ are at least one, and if $x\in X$ has an edge to $y$ then $d(x)\geq d(y)$. Show that there's a matching saturating X. I ...
1answer
38 views

0answers
21 views

### The product of an eigenvector and its transpose in a bipartite graph

I was reading this proof on the eigenvectors of a bipartite graph I don't really understand the 3rd line of this proof. How do we know if there even exists such an eigenvector x1 such that $x_1^T*x_1$ ...
0answers
19 views

### Assignment problem with batching costs

I am studying an assignment problem with batching costs, and I would like to know if there is a standard name or algorithm for this problem. I know this problem can be formulated as mixed-integer ...
1answer
39 views

### What is the adjacency matrix for k-regular graphs, and for bipartite graphs?

What is the adjacency matrix for $k-$regular graphs, and for bipartite graphs? I suppose that the general form for the adjacency matrix of a bipartite graph is: \begin{equation*} A_{K_{n,\: m}}=\begin{...
1answer
51 views

### Determine which are true and which are false | Graph Theory

From the following statements determine which are true and which are false. In each case justify your answer or give a counterexample. a) If a connected graph has cut vertices, then also it has ...
0answers
45 views

### Determine the set of cut vertices, bridges and number of connected components.

In the following graphs, determine the set of cut vertices, bridges and number of connected components when removing cut vertices or bridges: a) Complete graphs b) Bipartite graphs c) Path d) Cycles e)...
1answer
45 views

### A question about the constructive proof of Kőnig's Theorem

Kőnig's Theorem is as follows: If $G$ is a bipartite graph, then the maximum number of edges in a matching in $G$ is equal to the minimum number of vertices in a vertex cover in $G$. The constructive ...
1answer
32 views

### Laplacian of bipartite graph

It is well know that in the case of weighted graph with positive weights, the dimension of the kernel of the Laplacian is the number of connected components of the corresponding graph. This fails when ...
0answers
16 views

### Algorithm for splitting bipartite graph in a disjoint subset

I am looking for an algorithm to split a bipartite graph into disjoint subsets. The problem originates from analyzing a cross-correlation matrix, $C_{nm}$, between two sets of variables. I convert ...
0answers
29 views

### Is there any new developments on the Barnette's conjecture?

When I searching for interesting math problems. I find there is a graph theory conjecture called the Barnette's conjecture. The statement is: Is every bipartite simple polyhedron Hamiltonian? A early ...
2answers
56 views