154k views
2 votes
Each of the statements is false. Provide a counterexample to prove that each statement is false.

A. A bipartite graph with three vertices on one side and two on the other.
B. A bipartite graph with a vertex having an odd degree.
C. A non-bipartite graph with vertices having even degrees.
D. None of the above.

User Flown
by
7.7k points

1 Answer

0 votes

Final answer:

To prove the statements false, we need to provide counterexamples. For statement A, a counterexample would be a bipartite graph with three vertices on one side and two on the other. For statement B, a counterexample would be a bipartite graph with a vertex having an odd degree. For statement C, a counterexample would be a non-bipartite graph with vertices having even degrees.

Step-by-step explanation:

In order to prove that each of the statements is false, we need to provide counterexamples for them:

A. A bipartite graph with three vertices on one side and two on the other: A counterexample for this statement would be a bipartite graph where one side has three vertices (A, B, C) and the other side has two vertices (D, E). An example of this would be a graph with the edges AD, BD, CE.

B. A bipartite graph with a vertex having an odd degree: A counterexample would be a bipartite graph with vertices A, B, C on one side and vertices D, E on the other side. If we have edges connecting A to D, B to E, and C to D, we can see that vertex C has an odd degree.

C. A non-bipartite graph with vertices having even degrees: A counterexample for this statement would be a triangle with vertices A, B, C. Each vertex has an even degree, but the graph is non-bipartite.

D. None of the above: This statement is false because we have provided counterexamples for each of the given statements.

User Bharat Modi
by
7.9k points