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

705 questions
Filter by
Sorted by
Tagged with
35 views

### Prove: For any simple, connected, planar graph $G$, $e\le 3v-6$

Prove: For any simple, connected, planar graph $G$, $e\le 3v-6$ Let $G$ be a planar, simple, connected graph. $G$ is isomorphic to itself and thus, by the property of invariance, is also bipartite. By ...
73 views

### Maximal spectral norm of balanced $\pm 1$ matrix [closed]

Suppose that we have a square matrix $A = [a_{ij}] \in {\Bbb R}^{n \times n}$ whose entries are $\pm 1$ and whose columns are balanced, i.e., $\sum_{i=1}^n a_{ij}=0$. How large can the spectral norm ...
26 views

### Non-complete bipartite graph notation

How to denote a non-complete bipartite graphs? Because as far as I know, $K_{m, n}$ notation is only for complete bipartite graphs.
63 views

### Non-isomorphic bipartite Graphs with same degree sequence and cycles

I am still trying to understand the graph isomorphism problem for bipartite graphs. I know two bipartite graphs cannot be isomorphic if they do not possess the same degree sequence or not the same ...
26 views

### Prove that every bipartite graph G has a matching of size ≥ |E(G)|/∆, where ∆ is the maximum degree of G.

Prove that every bipartite graph G has a matching of size ≥ |E(G)|/∆, where ∆ is the maximum degree of G. Using Halls Theorem. I need a good proof, I am studying for an exam and I need to understand ...
24 views

### How to prove the existence of groups for bipartite graph?

I have a simple bipartite graph with bipartition (W, C) such that $|W| < |C|$, each vertex $c \in C$ has 2 edges (so to two different vertices w each time) and each vertex $w \in W$ has 4 edges. I ...
44 views

### Bipartiteness of hypercube graph with at least one edge contracted

I am participating in a research in my university and as a side task I need to solve the following problem: Consider a hypercube graph. Someone contracts one edge in it. What is the minimum number of ...
34 views

### Proving possibilities of building bipartite 2 colored graphs with n vertices

I want to show that I can you can build a two-colorable graph for all n that have n vertices and $\left\lfloor \frac{n^2}{4} \right\rfloor$ edges. After this, I want to show that it is impossible to ...
57 views

### At least n lines to cover all ones when each row and column has exactly k ones

Given is an $n{\times}n$ $(0, 1)$ matrix $A$. Prove that if in each row and in each column there are exactly $k$ ones, where $k\ge 1$, then it is impossible to cover all $1$s in the matrix using less ...
83 views

1 vote