Mathematics Stack Exchange
Mathematics Stack Exchange

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.

A bipartite graph is a graph $G=(V,E)$ such that the vertex set $V$ can be divided into two disjoint subsets such that no edge of $G$ joins two vertices from same subset. That is, $V=V_1\cup V_2$ such that $V_1\cap V_2=\emptyset$ and for any $e=uv\in E$, one of vertices among $u$ and $v$ belongs to $V_1$ and another belongs to $V_2$. There is no edge $e=uv\in E$ such that both $u$ and $v$ belongs to $V_1$ or both belongs to $V_2$.

740 questions
1
vote
1 answer

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$. It's for me clear, that if two shortest paths are…
toki
  • 95
1
vote
0 answers

A question regarding the Guth-Katz proof of the Joints problem

On page 7 of:http://arxiv.org/pdf/0812.1043.pdf Guth and Katz apply lemma 4.1 to prove that $|J_r|\geq 999/1000 |J|$. This application should be fairly trivial, but with a lot of staring I can't finish it. I'll give my best effort and hope to…
Michael King
  • 73
  • 5
1
vote
0 answers

Bipartite graph node coloring with $\{-1, +1\}$

What are the conditions that an undirected bipartite graph $G=(U,V, E)$ should have to be colored as follows: Nodes in $U$ are colored $-1$ or $+1$. The sign of a node $v \in V$ is the sum of the colors of the nodes in $U$ connected to $v$, i.e.…
Mostafa Dehghan
  • 11
0
votes
1 answer

Show that every graph has a bipartite subgraph with at least half of its edges

I know that there are solutions where we use induction. but i have a solution, and i think it is legit. let $c_1, c_2 ... , c_k$ be all the odd circles in graph $G$, the smallest circle would be a triangle , so we can remove from every one of them…
user2743516
  • 1