Understanding Bipartite and Named Graphs

This video tutorial introduces bipartite graphs, explaining how vertices can be divided into two sets with no internal adjacency. It covers complete bipartite graphs, denoted as Kmn, where each vertex in one set is connected to all vertices in the other. The tutorial also explores named graphs, including complete graphs (Kn), cycle graphs (Cn), and path graphs (Pn), providing examples and highlighting their unique properties.

What is a key characteristic of a bipartite graph?

• Vertices are divided into two sets with no internal connections.

• Each vertex is connected to exactly two other vertices.

• There are no edges in the graph.

• All vertices are connected to each other.

In a complete bipartite graph K_m,n, what does 'm' represent?

• The total number of vertices in the graph.

• The number of vertices in set A.

• The number of vertices in set B.

• The number of edges in the graph.

Which of the following is true for a complete bipartite graph?

• Each vertex is connected to exactly one other vertex.

• There are no edges between any vertices.

• Each vertex in one set is connected to all vertices in the other set.

• All vertices are in a single set.

What is a complete graph?

• A graph with no edges.

• A graph with only one vertex.

• A graph where each vertex is connected to exactly two other vertices.

• A graph where each pair of vertices is connected by exactly one edge.

What is the special notation for a complete graph with n vertices?

• C_n

• P_n

• K_n

• B_n

In the graph K_2,3, how many vertices are in set B?

• 6

• 2

• 5

• 3

What is a cycle graph C_n?

• A graph with n vertices and n edges forming a loop.

• A graph with n vertices and no edges.

• A graph with n vertices and n-1 edges.

• A graph with n vertices and 2n edges.

In a path graph P_n, what does 'n' represent?

• The number of vertices.

• The number of edges.

• The number of disconnected components.

• The number of loops.

In a cycle graph C_6, how many edges are there?

• 5

• 8

• 6

• 7

How many vertices are there in a path graph P_5?

• 4

• 5

• 7

• 6