Is any subgraph of a bipartite always bipartite? Prove, or give a counterexample.

Question

Question

Answer 1

Answer #1

We need to prove that any sub graph of a bipartite graph is bipartite.

A graph is called bipartite if with and every edge of G is of the form with and

Let be bipartite with the set of vertices V, partitioned as so that each edge in the set of edges E, is of the form where and

Let H be a subgraph of G and W denote the set of vertices for H.

Then, we have

Substituting we get

We have

Since H is a subgraph of G and if is an edge in H thenis an edge in G where, and then

Thus the subgraph H also satisfies the condition of a bipartite graph.

Therefore, H is a bipartite graph.

Hence, a sub graph of bipartite graph is bipartite.

Answer 2

Similar Homework Help Questions

Prove or give a counterexample: For any integers b and c and any positive integer m,...

Prove or give a counterexample: For any integers b and c and any positive integer m, if b ≡ c (mod m) then b + m ≡ c (mod m).
Theorem 2.4 Every loopless graph G contains a spanning bipartite subgraph F such that dr(v) >...

Theorem 2.4 Every loopless graph G contains a spanning bipartite subgraph F such that dr(v) > zdo(v) for all v E V. Let e(F) be the number of edges in graph F and let e(G) be the number of edges in graph G. Deduce from Theorem 2.4 that every loopless graph G contains a spanning bipartite subgraph F with e(F) > ze(G).
Prove or give a counterexample to the following statement: If the coefficient matrix of a system...

Prove or give a counterexample to the following statement: If the coefficient matrix of a system of m linear equations in n unknowns has rank m, then the system has a solution.

2. ** Prove or give a counterexample (a) If AC R is nonempty and open then...

2. ** Prove or give a counterexample (a) If AC R is nonempty and open then A contains a rational number (b) If ACR is bounded and open then A does not contain its supremum (c) The intersection of infinitely many open sets is open
P9.6.3 Prove that a connected undirected graph G is bipartite if and only if there are no edges b...

P9.6.3 Prove that a connected undirected graph G is bipartite if and only if there are no edges between nodes at the same level in any BFS tree for G. (An undirected graph is defined to be bipartite if its nodes can be divided into two sets X and Y such that all edges have one endpoint in X and the other in Y.) P9.6.3 Prove that a connected undirected graph G is bipartite if and only if there are...
5. (+5 each) Prove or t, check (False) and then give a counterexample and explain.iob no...

5. (+5 each) Prove or t, check (False) and then give a counterexample and explain.iob no len (1) If p is the projection of a vector b onto the space spanned by two linear independent vectors and a2, then p is the sum of two projections pi and p2, where pi and p2 are projections of b onto ãi and a2, respectively. disprove, i.e., if a statement is true, check (True) and then prove it: if (A(True/False) P A CAa...

For each of the following statements, either prove the statement or give a counterexample that shows...

For each of the following statements, either prove the statement or give a counterexample that shows the statement is false. We will use the (non-standard) notation I to represent the irrational numbers Each problem is worth 10 points. 1. For all mEN2, m2-1 is composite. 2. For all integers a and b If ab is even then a is even or b is even. 3. For all integers a, b, and c If ale and ble then ablc
Help please! Using matlab Prove or give a counterexample: if f: X rightarrow Y and g:...

Help please! Using matlab Prove or give a counterexample: if f: X rightarrow Y and g: Y rightarrow X are functions such that g o f = I_X and f o g = I_Y, then f and g are both one-to-one and onto and g = f^-1.
Prove the following: If G is bipartite, and is an eigenvalue of adjacency matrix A, then...

Prove the following: If G is bipartite, and is an eigenvalue of adjacency matrix A, then so is -1.

Give a counterexample to prove the following conjectures false, 21. All mammals live on land. 22....

Give a counterexample to prove the following conjectures false, 21. All mammals live on land. 22. If a number is even, then it is a multiple of four. 23. A number is only divisible by five, if the number ends in five. 24. Two odd numbers will have a sum that is odd. 25. All four-sided polygons have four right angles.