Bipartite graphs Flashcards
1
Q
What is a bipartite graph?
A
A graph in which the vertex set can be partitioned so that all vertices are in either A or B and there exists only edges between A and B
2
Q
A graph is bipartite iff…
A
It contains no odd cycles
3
Q
Every graph G contains a bipartite subgraph with at least ___ ___ ___ as G
A
as many edges
