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-?

1. An element of G is a vertex, point, or node of a set V=V(G).
2. Edges of G represent pairs of distinct vertices ordered by the set E = E(G).
3. Such a graph is denoted by G(V, E) if an edge e =[u, v] connects two adjacent vertices u and v.
4. All of the above

Answer: D) All of the above

Explanation:

Graph G consist of-

1. An element of G is a vertex, point, or node of a set V=V(G).
2. Edges of G represent pairs of distinct vertices ordered by the set E = E(G).
3. 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?

1. Vertex
2. Point
3. Endpoint
4. 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?

1. Points
2. Edges
3. Vertex
4. 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 ____?

1. Once
2. Twice
3. Thrice
4. Multiple times

Answer: B) Twice

Explanation:

Self-loops are counted twice.

---

5. Vertex degrees are represented by ____?

1. v(d)
2. v
3. d
4. 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?

1. n
2. n+1
3. n-1
4. n²

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?

1. Simple
2. Circuit
3. Closed
4. 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?

1. One
2. Two
3. Zero
4. Multiple

Answer: C) Zero

Explanation:

Paths with zero repeated vertex are called elementary paths.

---

9. ____ are paths with the same vertex at both ends?

1. Circuits paths
2. Closed paths
3. Both A and B
4. 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?

1. Elementary circuits
2. Closed circuits
3. Simple circuits
4. None of the above

Answer: C) Simple circuits

Explanation:

Simple circuits are paths that are circuits.

---

11. Pendant vertex is a vertex with degree ____?

1. Zero
2. One
3. Two
4. 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?

1. Odd
2. Even
3. Pendant
4. 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?

1. Odd
2. Even
3. Pendant
4. None

Answer: A) Odd

Explanation:

Odd vertex refers to a vertex with odd degree.

---

14. Even vertex refers to a vertex with ____ degree?

1. Odd
2. Even
3. Pendant
4. 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?

1. Two
2. Three
3. Four
4. 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 ____?

1. Cross
2. Adjacent
3. Normal
4. 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)?

1. Endpoint
2. Compliment
3. Adjacent
4. 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?

1. Same
2. Different
3. Similar
4. 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 __?

1. 0
2. 1
3. 2
4. 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?

1. Small
2. Cut
3. Disconnect
4. 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?

1. Cut Point
2. Cut Vertex
3. Both A and B
4. 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.?

1. Bridge
2. Cut Edge
3. Both A and B
4. 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.

---

---