### Engineering Mathematics - Mathematical Logic and Graph Theory

#### Question - 1

Let G be a non-planar graph with the minimum possible number of edges. Then, G has

• A 9 edges and 5 vertices
• B 9 edges and 6 vertices
• C 10 edges and 5 vertices
• D 10 edges and 6 vertices

#### Question - 2

Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is

• A 0
• B 8
• C 9
• D 13

#### Question - 3

Which one of the following is the most appropriate logical formula to represent the statement 'Gold and silver ornaments are precious'?
The following notations are used
G(x) : x is a gold ornament
S(x) : x is a silver ornament
P(x) : x is precious

• A $\forall x(P(x))\rightarrow (G(x)\wedge S(x))$
• B $\forall x(G(x)\wedge S(x)\rightarrow P(x))$
• C $\exists x((G(x)\wedge S(x))\rightarrow P(x))$
• D $\forall x((G(x)\wedge S(x))\rightarrow P(x))$

#### Question - 4

P and Q two propositions. Which of the following logical expressions are equivalent?
$1.\quad P\wedge \sim Q\\ 2.\quad \sim (\sim P\wedge Q)\\ 3.\quad (P\wedge Q)\vee (P\wedge \sim Q)\vee (\sim P\wedge \sim Q)\\ 4.\quad (P\wedge Q)\vee (P\wedge \sim Q)\vee (\sim P\wedge Q)$

• A 1 and 2
• B 1, 2 and 3
• C 1, 2 and 4
• D All of 1, 2, 3 and 4

#### Question - 5

Let graph (x) be a predicate which denotes that x is a graph. Let connected (x) be predicate which denotes that x is connected. Which of the following first order logic sentences does not represent the statement 'Not every graph is connected'?

• A $\neg \forall$ x (graph(x)$\Rightarrow$connected(x))
• B $\exists x(graph(x)\wedge \neg connected(x))$
• C $\neg \forall (\neg graph(x)\vee connected(x))$
• D $\forall x(graph(x))\Rightarrow \neg connected(x))$

#### Question - 6

Which one of the first order predicate calculus statements given below, correctly expresses the following english statement?
Tiger and lions attack, if they are hungry or threatened.

• A $\forall x$ [(tiger (x) $\wedge$ lion (x))$\rightarrow${(hungry (x) $\vee$ threatened (x))$\rightarrow$attacks(x))}]
• B $\forall x$ [(tiger (x) $\vee$ lion (x))$\rightarrow${(hungry (x) $\vee$ threatened (x))$\rightarrow$attacks(x))}]
• C $\forall x$ [(tiger (x) $\vee$ lion (x))$\rightarrow${(attacks(x)$\rightarrow$hungry (x) $\vee$ threatened (x))}]
• D $\forall x$ [(tiger (x) $\vee$ lion (x))$\rightarrow${(hungry (x) $\vee$ threatened (x))$\rightarrow$attacks(x))}]

#### Question - 7

What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n $\ge$ 2

• A 2
• B 3
• C n-1
• D n

#### Question - 8

Which one of the following is true for any simple connected undirected graph with more than 2 vertices?

• A No two vertices have the same degree
• B Atleast two vertices have the same degree
• C Atleast three vertices have the same degree
• D All vertices have the same degree

#### Question - 9

Consider the following propositional statements
${ P }_{ 1 }:((A\wedge B)\rightarrow C)\equiv ((A\rightarrow C)\wedge (B\rightarrow C))$
${ P }_{ 2 }:((A\vee B)\rightarrow C)\equiv ((A\rightarrow C)\vee (B\rightarrow C))$
Which one of the following is true?

• A P1 is a tautology, but not P2
• B P2 is a tautology, but not P1
• C P1 and P2 are both tautologies
• D Both P1 and P2 are not tautologies

#### Question - 10

Let P, Q and R be three atomic propositional assertions. Let X denotes (P V Q) $\rightarrow$ R and Y denotes $(P\rightarrow R)\nu (Q\rightarrow R)$. Which one of the following is a tautology?

• A $X\equiv Y$
• B $X\rightarrow Y$
• C $Y\rightarrow X$
• D $\rightharpoondown Y\rightarrow X$