Module - 4

1. If a graph is Eulerian, then it must be:

A. Connected
B. Disconnected
C. Planar
D. Bipartite

2. In a simple undirected graph, the minimum degree is 2 and the maximum degree is 5. Which of the following statements is true?

A. The graph must have vertices with degrees ranging from 2 to 5
B. The graph must have a vertex of degree 6
C. The graph must have a vertex of degree 4
D. The graph must have a vertex of degree 7

3. Which of the following is a characteristic of a bipartite graph?

A. It has loops
B. It has parallel edges
C. It can be divided into two sets of vertices such that all edges connect vertices from different sets
D. It is a complete graph

4. If a graph has 8 vertices and 12 edges, then the degree of each vertex in the graph is:

A. 3
B. 6
C. 12
D. 10

5. What is a complete graph?

A. A graph in which every vertex is connected to every other vertex
B. A graph with no edges
C. A graph with only one vertex
D. A graph with parallel edges

6. A simple directed graph in which every pair of distinct vertices is connected by an edge in both directions is called:

A. Connected graph
B. Eulerian graph
C. Strongly connected graph
D. Weakly connected graph

7. The necessary and sufficient condition for a graph to be Eulerian is:

A. All vertices have even degree
B. All vertices have odd degree
C. All vertices have the same degree
D. There is a path between every pair of vertices

8. The sum of degrees of all vertices in a simple undirected graph is always:

A. Equal to the number of vertices in the graph
B. Twice the number of vertices in the graph
C. Equal to the number of edges in the graph
D. Half the number of edges in the graph

9. Consider a simple undirected graph with 6 vertices. The degrees of the vertices in this graph are as follows: vertex A has degree 3, vertex B has degree 2, vertex C has degree 4, vertex D has degree 3, vertex E has degree 3, and vertex F has degree 1. Calculate the number of edges in the graph.

A. 6
B. 7
C. 8
D. 12

10. How many edges does a complete graph on 5 vertices have?

A. 5
B. 10
C. 15
D. 20

11. In an Euler graph, a trail that visits every edge exactly once is called:

A. Hamiltonian cycle
B. Eulerian cycle
C. Eulerian path
D. Hamiltonian path

12. What is a multigraph?

A. A graph with multiple components
B. A graph with loops and parallel edges
C. A graph with no cycles
D. A graph with no vertices

13. A graph has 6 vertices, and each vertex has a degree of 2 except for one vertex, which has a degree of 4. Determine the number of edges in the graph.

A. 4
B. 7
C. 12
D. 16

14. How many edges does a bipartite graph on m and n vertices have?

A. mn
B. m+n
C. m+n-1
D. m+n+1

15. A simple undirected graph with all vertices having the same degree is called:

A. Complete graph
B. Bipartite graph
C. Regular graph
D. Eulerian graph

16. A complete graph on n vertices has how many edges?

A. n
B. n-1
C. n(n-1)/2
D. 2n

17. A Hamiltonian graph is a graph that contains:

A. No cycles
B. A cycle that visits every vertex exactly once
C. A path that visits every vertex exactly once
D. Only isolated vertices