Home »
MCQs »
Discrete Mathematics MCQs
Discrete Mathematics | Graph MCQs
Discrete Mathematics | Graph MCQs: This section contains multiple-choice questions and answers on Graph in Discrete Mathematics.
Submitted by Anushree Goswami, on July 27, 2022
1. Graph G consist of-?
- An element of G is a vertex, point, or node of a set V=V(G).
- Edges of G represent pairs of distinct vertices ordered by the set E = E(G).
- Such a graph is denoted by G(V, E) if an edge e =[u, v] connects two adjacent vertices u and v.
- All of the above
Answer: D) All of the above
Explanation:
Graph G consist of-
- An element of G is a vertex, point, or node of a set V=V(G).
- Edges of G represent pairs of distinct vertices ordered by the set E = E(G).
- Such a graph is denoted by G(V, E) if an edge e =[u, v] connects two adjacent vertices u and v.
2. The ____ of e=[u, v] are said to be u and v when e connects them?
- Vertex
- Point
- Endpoint
- Node
Answer: C) Endpoint
Explanation:
The endpoints of e=[u, v] are said to be u and v when e connects them.
3. Vertex degrees are calculated based on the number of ____ that are incident on the vertex?
- Points
- Edges
- Vertex
- Point
Answer: B) Edges
Explanation:
Vertex degrees are calculated based on the number of edges that are incident on the vertex.
4. Self-loops are counted ____?
- Once
- Twice
- Thrice
- Multiple times
Answer: B) Twice
Explanation:
Self-loops are counted twice.
5. Vertex degrees are represented by ____?
- v(d)
- v
- d
- d(v)
Answer: D) d(v)
Explanation:
Vertex degrees are represented by d(v).
6. Every pair of vertices in a graph is an edge, so a path of length n is a sequence of ___ vertices?
- n
- n+1
- n-1
- n2
Answer: B) n+1
Explanation:
Every pair of vertices in a graph is an edge, so a path of length n is a sequence of n+1 vertices.
7. When there is no repetition of edges in the path, it is called a ____ path?
- Simple
- Circuit
- Closed
- Elementary
Answer: A) Simple
Explanation:
When there is no repetition of edges in the path, it is called a simple path.
8. Paths with ___ repeated vertex are called elementary paths?
- One
- Two
- Zero
- Multiple
Answer: C) Zero
Explanation:
Paths with zero repeated vertex are called elementary paths.
9. ____ are paths with the same vertex at both ends?
- Circuits paths
- Closed paths
- Both A and B
- None of the above
Answer: C) Both A and B
Explanation:
Circuits or closed paths are paths with the same vertex at both ends.
10. ____are simple paths that are circuits?
- Elementary circuits
- Closed circuits
- Simple circuits
- None of the above
Answer: C) Simple circuits
Explanation:
Simple circuits are paths that are circuits.
11. Pendant vertex is a vertex with degree ____?
- Zero
- One
- Two
- Three
Answer: B) One
Explanation:
Pendant vertex is a vertex with degree one.
12. Pendant Edges are the only edges which are incident that occur with ____ vertices?
- Odd
- Even
- Pendant
- None
Answer: C) Pendant
Explanation:
Pendant Edges are the only edges which are incident that occur with pendant vertices.
13. Odd vertex refers to a vertex with ____ degree?
- Odd
- Even
- Pendant
- None
Answer: A) Odd
Explanation:
Odd vertex refers to a vertex with odd degree.
14. Even vertex refers to a vertex with ____ degree?
- Odd
- Even
- Pendant
- None
Answer: B) Even
Explanation:
Even vertex refers to a vertex with even degree.
15. An edge that connects ____ vertices is called an incident edge?
- Two
- Three
- Four
- Multiple
Answer: A) Two
Explanation:
An edge that connects two vertices is called an incident edge.
16. If an edge connects two vertices, they are considered ____?
- Cross
- Adjacent
- Normal
- Incident
Answer: B) Adjacent
Explanation:
If an edge connects two vertices, they are considered adjacent.
17. The vertex u is _____ to the vertex v, and the vertex v is adjacent to the vertex u if there is an edge (u, v)?
- Endpoint
- Compliment
- Adjacent
- Cross Join
Answer: C) Adjacent
Explanation:
The vertex u is adjacent to the vertex v, and the vertex v is adjacent to the vertex u if there is an edge (u, v).
18. If the edge has the _____ endpoint, it is called a self-loop?
- Same
- Different
- Similar
- Various
Answer: A) Same
Explanation:
If the edge has the same endpoint, it is called a self-loop.
19. Isolated vertex refers to a vertex with degree __?
- 0
- 1
- 2
- Null
Answer: A) 0
Explanation:
Isolated vertex refers to a vertex with degree 0.
20. ____ sets are smallest sets of edges from the graph so that removing the set disconnects the graph, but removing any appropriate subset leaves it connected?
- Small
- Cut
- Disconnect
- Subset
Answer: B) Cut
Explanation:
Cut sets are smallest sets of edges from the graph so that removing the set disconnects the graph, but removing any appropriate subset leaves it connected.
21. In a graph G, a _____ is a vertex v with more connected components than G?
- Cut Point
- Cut Vertex
- Both A and B
- None of the above
Answer: C) Both A and B
Explanation:
In a graph G, a Cut Point or Cut Vertex is a vertex v with more connected components than G.
22. In a graph, a ____ is an edge e with more connected components than G.?
- Bridge
- Cut Edge
- Both A and B
- None of the above
Answer: C) Both A and B
Explanation:
In a graph, a Bridge or Cut Edge is an edge e with more connected components than G.