Understanding Graphs and Trees

The video tutorial explores the maximum number of edges possible in different types of graphs with seven vertices. It begins with a complete graph, explaining that the maximum number of edges is 21, using the handshake lemma. It then examines bipartite graphs, determining that the maximum number of edges is 12 in a complete bipartite graph K3,4. Finally, it discusses trees, stating that the maximum number of edges is six, as a tree with n vertices always has n-1 edges.

What is the Handshake Lemma used for in graph theory?

• To identify cycles in a graph

• To calculate the number of vertices in a graph

• To determine the sum of the degrees of vertices

• To find the shortest path in a graph

In a complete graph with seven vertices, how many edges are there?

• 28

• 21

• 35

• 14

Which of the following is true for a complete graph?

• It is always bipartite

• It has more vertices than edges

• Each vertex is connected to every other vertex

• It has no edges

What is the degree of each vertex in a complete graph with seven vertices?

• 8

• 5

• 6

• 7

What is a characteristic of a complete bipartite graph?

• It has the same number of vertices in each set

• All vertices are connected to each other

• Vertices are divided into two sets with no internal connections

• It contains cycles

How many edges does a complete bipartite graph K3,4 have?

• 10

• 16

• 12

• 14

In a bipartite graph, what is the maximum number of edges possible with seven vertices?

• 10

• 11

• 12

• 13

What defines a tree in graph theory?

• A graph with cycles

• A graph with no cycles

• A graph with only one vertex

• A graph with equal number of vertices and edges

How many edges are there in a tree with seven vertices?

• 8

• 6

• 5

• 7

What is the general rule for the number of edges in a tree with n vertices?

• 2n

• n

• n + 1

• n - 1