Graph Theory Concepts Assessment

What is a connected graph?

• A connected graph is a graph where there is a path between every pair of vertices.

• A connected graph has no edges between vertices.

• A connected graph is a graph with at least one vertex.

• A connected graph is a graph where all vertices are isolated.

Define a complete graph.

• A complete graph is a graph where all vertices are isolated.

• A complete graph is a graph with only one vertex.

• A complete graph has no edges between any vertices.

• A complete graph is a graph where every pair of distinct vertices is connected by a unique edge.

What is the difference between a walk and a path?

• A walk is a straight line, while a path is a curved line.

• A path can only be taken once; a walk can be taken multiple times.

• A walk is a shorter route than a path.

• A walk allows repeated vertices; a path does not.

How is the degree of a vertex defined?

• The degree of a vertex is the total number of vertices in the graph.

• The degree of a vertex is the number of edges incident to it.

• The degree of a vertex is the average length of all edges connected to it.

• The degree of a vertex is the maximum weight of the edges incident to it.

What characterizes a bipartite graph?

• A graph that can be colored with three colors.

• A graph with all vertices connected to each other.

• A graph whose vertices can be divided into two disjoint sets with no edges within the same set.

• A graph that contains cycles of odd length.

Explain what a complete bipartite graph is.

• A complete bipartite graph is a graph where no vertices are connected.

• A complete bipartite graph has only one set of vertices.

• A complete bipartite graph consists of three sets of vertices.

• A complete bipartite graph is a graph that can be divided into two sets of vertices such that every vertex from one set is connected to every vertex in the other set.

Can a complete graph be bipartite? Why or why not?

• A complete graph is always bipartite regardless of the number of vertices.

• Yes, a complete graph can be bipartite if it has three vertices.

• A complete graph can be bipartite if it has an even number of vertices.

• No, a complete graph cannot be bipartite if it has more than two vertices.

What is the maximum degree of a vertex in a complete graph with n vertices?

• n + 1

• n - 1

• n/2

• n

How many edges does a complete bipartite graph K(m,n) have?

• m * n

• m + n

• m / n

• m - n

What is the significance of walks in graph theory?

• Walks are only used for calculating graph weights.

• Walks are significant for analyzing connectivity and traversal in graphs.

• Walks are irrelevant in understanding graph structures.

• Walks are primarily for aesthetic purposes in graph drawings.