SEC - I - Graph Theory

Which of the following is a simple graph?

• A graph with multiple edges between two vertices

• A graph with loops

• A graph with neither loops nor multiple edges

• A graph with at least one loop

In an undirected graph, the sum of the degrees of all vertices is equal to:

• Number of vertices

• Twice the number of edges

• Number of edges

• Square of the number of vertices

A connected graph with n vertices and (n−1) edges is called a:

• Tree

• Cycle

• Complete graph

• Null graph

The maximum number of edges in a simple graph with n vertices is:

• n²

• n(n−1)/2

• n(n+1)/2

• (n−1)

A graph is said to be connected if:

• Every vertex has the same degree

• There is a path between every pair of vertices

• It contains a cycle

• It has no isolated vertex

A complete graph with 5 vertices has how many edges?

• 5

• 10

• 15

• 20

A graph with no cycles is called a:

• Simple graph

• Complete graph

• Tree

• Connected graph

The degree of a vertex in an undirected graph is:

• The number of vertices adjacent to it

• The number of edges incident to it

• Always even

• The sum of all vertex labels

A graph that can be drawn without any edges crossing is called:

• A) Bipartite graph

• B) Planar graph

• C) Directed graph

• D) Weighted graph

In a directed graph, an edge is represented as:

• (u, v)

• {u, v}

• [u, v]

• <u, v>