### Multiple Choice Questions On Discrete Structure - Set 2

1) A graph is a collection of.... ?
1. Row and columns
2. Vertices and edges
3. Equations
4. None of these
Explanation: A graph contains the edges and vertices

2)  The degree of any vertex of graph is .... ?
1. The number of edges incident with vertex
2. Number of vertex in a graph
3. Number of vertices adjacent to that vertex
4. Number of edges in a graph
Explanation: The number of edges connected on a vertex v with the self loop counted twice is called the degree of vertex.

3) If for some positive integer k, degree of vertex d(v)=k for every vertex v of the graph G, then G is called... ?
1. K graph
2. K-regular graph
3. Empty graph
4. All of above
Explanation:  A graph in which all vertices are of equal degree is called regular graph.

4) A graph with no edges is known as empty graph. Empty graph is also known as... ?
1. Trivial graph
2. Regular graph
3. Bipartite graph
4. None of these
Explanation: Trivial graph is the second name for empty graph.

5) Length of the walk of a graph is .... ?
1. The number of vertices in walk W
2. The number of edges in walk W
3. Total number of edges in a graph
4. Total number of vertices in a graph
Explanation:  A walk is defined as finite altering sequence of vertices and edges. No Edges appear more than once but vertex may appear more than once.

6) If the origin and terminus of a walk are same, the walk is known as... ?
1. Open
2. Closed
3. Path
4. None of these
Explanation:  A walk which  begins and ends with same vertex is called closed walk otherwise it is open.

7) A graph G is called a ..... if it is a connected acyclic graph ?
1. Cyclic graph
2. Regular graph
3. Tree
4. Not a graph
Explanation: No explanation for this question.

8) Eccentricity of a vertex denoted by e(v) is defined by.... ?
1. max { d(u,v): u belongs to v, u does not equal to v : where d(u,v) is the distance between u&v}
2. min { d(u,v): u belongs to v, u does not equal to v }
3. Both A and B
4. None of these
Explanation:  The eccentricity E(v) of a vertex V in the graph is the distance from v to the vertex farthest from v in G.

9) Radius of a graph, denoted by rad(G) is defined by.... ?
1. max {e(v): v belongs to V }
2. min { e(v):  v belongs to V}
3. max { d(u,v): u belongs to v, u does not equal to v }
4. min { d(u,v): u belongs to v, u does not equal to v }
Explanation:  The diameter or radius of a graph G is largest distance between two vertices in the graph G.

10) The complete graph K, has... different spanning trees?
1. nn-2
2. n*n
3. nn
4. n2