Bipartite Graphs Quiz

Which of the following graphs is a bipartite graph?

• A graph with an odd-length cycle

• A graph with no cycles

• A graph with a single vertex

• A complete graph with 5 vertices

A graph is bipartite if and only if it does not contain which of the following?

• An even-length cycle

• A self-loop

• An odd-length cycle

• A complete subgraph

Which of the following properties is true for all bipartite graphs?

• They have an even number of vertices

• They can be coloured using two colours such that no two adjacent vertices share the same colour

• They contain at least one cycle

• They are always connected

• Depth-First Search (DFS)

• Breadth-First Search (BFS)

• Dijkstra's Algorithm

• Kruskal's Algorithm

Which of the following is a real-world example of a bipartite graph?

• A social network where people are connected if they are friends

• A job assignment problem where jobs are connected to people who can perform them

• A transportation network where cities are connected by roads

• A computer network where computers are connected by cables

If a bipartite graph has 10 vertices and 15 edges, what is the maximum number of edges that can be added without losing its bipartite property?

• 10

• 15

• 20

• 25

Which of the following is NOT a characteristic of a bipartite graph?

• It can be divided into two disjoint sets

• It contains no odd-length cycles

• It can be coloured with two colours

• It must be a planar graph

In a bipartite graph, the sum of the degrees of all vertices in one set is equal to:

• The number of vertices in the other set

• The sum of the degrees of all vertices in the other set

• Twice the number of edges

• Half the number of edges

Which of the following graphs is always bipartite?