GATE CSE 2015 Set 1 | Graph Theory Question 27 | Discrete Mathematics

GATE CSE 2015 Set 1

MCQ (Single Correct Answer)

-0.6

Suppose L = { p, q, r, s, t } is a lattice represented by the following Hasse diagram: GATE CSE 2015 Set 1 Discrete Mathematics - Graph Theory Question 28 English

GATE CSE 2015 Set 1 Discrete Mathematics - Graph Theory Question 28 English

For any $$x, y ∈ L$$, not necessarily distinct, $$x ∨ y$$ and x ∧ y are join and meet of x, y, respectively. Let $$L^3 = \left\{\left(x, y, z\right): x, y, z ∈ L\right\}$$ be the set of all ordered triplets of the elements of L. Let p_r be the probability that an element $$\left(x, y,z\right) ∈ L^3$$ chosen equiprobably satisfies $$x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)$$. Then

p_r = 0

p_r = 1

$$0 < p_r ≤ \frac{1}{5}$$

$$\frac{1}{5} < p_r < 1$$

GATE CSE 2015 Set 1

Numerical

-0

Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is ___________.

Your input ____

GATE CSE 2014 Set 3

MCQ (Single Correct Answer)

-0.6

If $$G$$ is a forest with $$n$$ vertices and $$k$$ connected components, how many edges does $$G$$ have?

$$\left\lfloor {n/k} \right\rfloor $$

$$\left\lceil {n/k} \right\rceil \,$$

$$n - k$$

$$n - k + 1$$

GATE CSE 2014 Set 3

MCQ (Single Correct Answer)

-0.6

Let $$\delta $$ denote the minimum degree of a vertex in a graph. For all planar graphs on $$n$$ vertices with $$\delta \ge 3$$, which one of the following is TRUE?

In any planar embedding, the number of faces is at least $${n \over 2} + 2$$

In any planar embedding, the number of faces is less than $${n \over 2} + 2$$

There is a planar embedding in which the number of facess is less than $${n \over 2} + 2$$

There is a planar embedding in which the number of faces is at most $${n \over {\delta + 1}}$$

PREVIOUS NEXT