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
- n
^{2}

**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.

Comments and Discussions!