**1) Let A and B be any two arbitrary events then which one of the following is true ?**

- P( A intersection B) = P(A). P(B)
- P(A union B) = P(A) + P(B)
- P(AB) = P(A intersection B). P(B)
- P(A union B) >= P(A) + P(B)

Collection From:
www.cs-mcqs.blogspot.com

**Answer = D**

**2) If X and Y be the sets. Then the set ( X - Y) union (Y- X) union (X intersection Y ) is equal to?**

- X union Y
- X
^{c}union Y^{c} - X intersection Y
- X
^{c}intersection Y^{c}

Collection From:
www.cs-mcqs.blogspot.com

**Answer = A**

**3) If G is an undirected planer graph on n vertices with e edges then ?**

- e<=n
- e<=2n
- e<=3n
- None of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

**4) Which of the following statement is false ?**

- G is connected and is circuitless
- G is connected and has n edges
- G is minimally connected graph
- G is circuitless and has n-1 edges

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

**5) Probability that two randomly selected cards from a set of two red and two black cards are of same color is ?**

- 1 / 2
- 1 / 3
- 2 / 3
- None of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

**6) The number of circuits that can be created by adding an edge between any two vertices in a tree is ?**

- Two
- Exactly one
- At least two
- None

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

**7) In a tree between every pair of vertices there is ?**

- Exactly one path
- A self loop
- Two circuits
- n number of paths

Collection From:
www.cs-mcqs.blogspot.com

**Answer = A**

**8) The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from some same suit is ?**

- 8
- 3
- 9
- 12

Collection From:
www.cs-mcqs.blogspot.com

**Answer = C**

**9) Context free languages are closed under ?**

- union, intersection
- Intersection , complement
- union , kleene star
- Complement , kleene star

Collection From:
www.cs-mcqs.blogspot.com

**Answer = C**

**10) Let R be a symmetric and transitive relation on a set A. Then ?**

- R is reflexive and hence a partial order
- R is reflexive and hence an equivalence relation
- R is not reflexive and hence not an equivalence relation
- None of above

Collection From:
www.cs-mcqs.blogspot.com

**Answer = D**

**SET-2**

**1) A graph is a collection of.... ?**

- Row and columns
- Vertices and edges
- Equations
- None of these

Collection From: www.cs-mcqs.blogspot.com

**Answer = B**

**Explanation: A graph contains the edges and vertices**

**2) The degree of any vertex of graph is .... ?**

- The number of edges incident with vertex
- Number of vertex in a graph
- Number of vertices adjacent to that vertex
- Number of edges in a graph

Collection From:
www.cs-mcqs.blogspot.com

**Answer = A**

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

- K graph
- K-regular graph
- Empty graph
- All of above

Collection From:
www.cs-mcqs.blogspot.coms

**Answer = B**

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

- Trivial graph
- Regular graph
- Bipartite graph
- None of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = A**

**Explanation: Trivial graph is the second name for empty graph.**

**5) Length of the walk of a graph is .... ?**

- The number of vertices in walk W
- The number of edges in walk W
- Total number of edges in a graph
- Total number of vertices in a graph

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

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

- Open
- Closed
- Path
- None of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

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

- Cyclic graph
- Regular graph
- Tree
- Not a graph

Collection From: www.cs-mcqs.blogspot.com

**Answer = C**

**Explanation: No explanation for this question.**

**8) Eccentricity of a vertex denoted by e(v) is defined by.... ?**

- max { d(u,v): u belongs to v, u does not equal to v : where d(u,v) is the distance between u&v}
- min { d(u,v): u belongs to v, u does not equal to v }
- Both A and B
- None of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = A**

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

- max {e(v): v belongs to V }
- min { e(v): v belongs to V}
- max { d(u,v): u belongs to v, u does not equal to v }
- min { d(u,v): u belongs to v, u does not equal to v }

Collection From:
www.cs-mcqs.blogspot.com

**Answer = A**

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

- n
^{n-2} - n*n
- n
^{n} - n
^{2}

Collection From:
www.cs-mcqs.blogspot.com

**Answer = A**

**Explanation: No explanation for this question.**

SET-3

**1) A tour of G is a closed walk of graph G which includes every edge G at least once. A ..... tour of G is a tour which includes every edge of G exactly once ?**

- Hamiltonian
- Planar
- Isomorphic
- Euler

Collection From:
www.cs-mcqs.blogspot.com

**Answer = D**

**Explanation: If some closed walk in a graph contains all the edges then the walk is called Euler.**

**2) Which of the following is not a type of graph ?**

- Euler
- Hamiltonian
- Tree
- Path

Collection From:
www.cs-mcqs.blogspot.com

**Answer = D**

**Explanation:Path is a way from one node no another but not a graph.**

**3) Choose the most appropriate definition of plane graph ?**

- A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices
- A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non - empty disjoint subset X and Y in such a way that each edge of G has one end in X and one end in Y.
- A simple graph which is Isomorphic to Hamiltonian graph
- None of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = A**

**Explanation: No explanation for this question.**

**4) A continuous non - intersecting curve in the plane whose origin and terminus coincide ?**

- Planer
- Jordan
- Hamiltonian
- All of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

**Explanation: The jordan graph is the set of all vertices of minimum eccentricity that is the set of all vertices A where the greatest distance to other vertex B is minimal.**

**5) Polyhedral is.... ?**

- A simple connected graph
- A plane graph
- A graph in which the degree of every vertex and every face is atleast 3
- All of above

Collection From:
www.cs-mcqs.blogspot.com

**Answer = D**

**Explanation: A polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron**

**6) A path in graph G, which contains every vertex of G once and only once ?**

- Eulartour
- Hamiltonian Path
- Eular trail
- Hamiltonian tour

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

**Explanation:A Hamiltonian circuit in a connected graph is defined as a closed walk that traverse every vertex of G exactly once except the starting vertex.**

**7) A minimal spanning tree of a graph G is.... ?**

- A spanning sub graph
- A tree
- Minimum weights
- All of above

Collection From:
www.cs-mcqs.blogspot.com

**Answer = D**

**Explanation: A tree is said to be spanning tree of connected graph G if it is subgraph of G and contains all the vertices of G.**

**8) A tree having a main node, which has no predecessor is.... ?**

- Spanning tree
- Rooted tree
- Weighted tree
- None of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

**Explanation:A tree in which one vertex distinguish from all other is called rooted tree.**

**9) Diameter of a graph is denoted by diam(G) is defined by.... ?**

- max (e(v) : v belongs to V)
- max( d(u,v) )
- Both A and B
- None of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = C**

**Explanation: The diameter of a graph G is largest distance between two vertices in a graph G.**

**10) A vertex of a graph is called even or odd depending upon ?**

- Total number of edges in a graph is even or odd
- Total number of vertices in a graph is even or odd
- Its degree is even or odd
- None of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = C**

**Explanation: The vertex of a graph is called even or odd based on its degree.**

SET-4

**1) Let A and B be any two arbitrary events then which one of the following is true ?**

- P( A intersection B) = P(A). P(B)
- P(A union B) = P(A) + P(B)
- P(AB) = P(A intersection B). P(B)
- P(A union B) >= P(A) + P(B)

Collection From:
www.cs-mcqs.blogspot.com

**Answer = D**

**2) If X and Y be the sets. Then the set ( X - Y) union (Y- X) union (X intersection Y ) is equal to?**

- X union Y
- X
^{c}union Y^{c} - X intersection Y
- X
^{c}intersection Y^{c}

Collection From:
www.cs-mcqs.blogspot.com

**Answer = A**

**3) If G is an undirected planer graph on n vertices with e edges then ?**

- e<=n
- e<=2n
- e<=3n
- None of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

**4) Which of the following statement is false ?**

- G is connected and is circuitless
- G is connected and has n edges
- G is minimally connected graph
- G is circuitless and has n-1 edges

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

- 1 / 2
- 1 / 3
- 2 / 3
- None of these

Collection From:
www.cs-mcqs.blogspot.com

**Answer = B**

- Two
- Exactly one
- At least two
- None

Collection From: www.cs-mcqs.blogspot.com

**Answer = B**

**7) In a tree between every pair of vertices there is ?**

- Exactly one path
- A self loop
- Two circuits
- n number of paths

Collection From:
www.cs-mcqs.blogspot.com

**Answer = A**

- 8
- 3
- 9
- 12

Collection From:
www.cs-mcqs.blogspot.com

**Answer = C**

**9) Context free languages are closed under ?**

- union, intersection
- Intersection , complement
- union , kleene star
- Complement , kleene star

Collection From:
www.cs-mcqs.blogspot.com

**Answer = C**

**10) Let R be a symmetric and transitive relation on a set A. Then ?**

- R is reflexive and hence a partial order
- R is reflexive and hence an equivalence relation
- R is not reflexive and hence not an equivalence relation
- None of above

Collection From:
www.cs-mcqs.blogspot.com

**Answer = D**