Explore topic-wise InterviewSolutions in .

Right answer is (C) 2

The best explanation: We know that sum of DEGREES of all vertices = 2X no of edges. Say number of edges is E. Degree of LAST vertex is x, 1+2+3+4+5+6+7++8+9+x = 2XE

=>45+x = 2XE

Now putting options we get answer 0 or 5

But one vertex of degree 9 means it connected to all other VERTEXES. So, the degree must be 5.

Correct CHOICE is (b) BIPARTITE GRAPH

For explanation I would SAY: In graph theory, most common graphs are CONSIDERED to be finite otherwise it is an infinite graph. Now, a finite graph is a graph in which the vertex set and the edge set are described as the finite sets.

Right CHOICE is (d) more than 10

Best EXPLANATION: In an undirected triangle-free graph no three vertices can form a triangle of edges. It can be described as graphs with clique number less than 2 and the graphs with girth greater than 4.

Correct choice is (a) 24

Explanation: A vertex COLOURING of a graph G = (V’,E’) with m colours is a mapping F:V’ -> {1,…,m}such that f(u)!=f(v) for every (u,v) belongs to E’. SINCE in worst CASE the graph can be complete, d+1 colours are necessary for graph containing vertices with degree at most ‘d’. So, the required answer is 24.

Right option is (c) 360

The explanation is: A HAMILTONIAN CYCLE in a CONNECTED graph G is defined as a closed path that traverses every vertex of G exactly once EXCEPT the STARTING vertex, at which the path also terminates. In an n-complete graph, there are (n-1)!/2 hamiltonian cycles and so the answer is 360.

Right OPTION is (C) COMPLETE GRAPH

Easy explanation: The below bipartite graph is not a complete graph as there is no edge between A-B, B-C, C-D, C-Q, P-Q, Q-R, Q-D and so it is not a complete graph.

Right choice is (a) SYMMETRY, bipartite

The explanation: A graph is bipartite if and only if it does not CONTAIN an ODD cycle. The SPECTRUM of a graph is symmetric if and only if it is a bipartite graph. These are the characteristics of the graph.

Right answer is (a) modern CODING theory

Easy explanation: All types of cyclic graphs are examples of cyclic graphs. A cyclic graph is CONSIDERED bipartite if all the cycles INVOLVED are of even length. Bipartite graphs are widely used in modern coding theory apart from being used in MODELING relationships.

Correct answer is (b) null

Easiest EXPLANATION: In a complete Bipartite graph, there must exist a partition say, V(G)=X∪Y and X∩Y=∅, that MEANS all edges share a vertex from both set X and Y.

Right choice is (b) linear time

The best explanation: It is possible to test whether a graph is bipartite, and to return EITHER a two-coloring (if it is bipartite) or an ODD cycle (if it is not) in linear time i.e, O(n) using depth first search. In case of the intersection of n line segments or other simple SHAPES in the EUCLIDEAN graph, it is possible to test whether the graph is bipartite and it will return either a two-coloring or an odd cycle in time O(nlogn), even though the graph itself has up to O(n^2) edges.

Right answer is (d) 49

To ELABORATE: By definition, the maximum possible number of EDGES in a bipartite graph on ‘n’ VERTICES = (1/4) X n^2.

Substituting n = 14, we get maximum number of edges in a bipartite graph on 14 vertices,= (1/4) x (14)^2

= (1/4) x 14 x 14

= 49

∴ Maximum number of edges in a bipartite graph on 14 vertices = 49.

Right CHOICE is (b) 2-VERTEX set of G1

For explanation I would say: A graph G1(V, E) is called bipartite if its vertex set V(G) can be decomposed into two non-empty disjoint subsets V1(G1) and V2(G1) in such a way that each EDGE e ∈ E(G) has its one end joint in V1(G1) and other endpoint in V2(G1). The partition V = V1 ∪ V2 in a bipartite graph G1 is called bipartition of G1.

Right choice is (c) 49

Easiest explanation: Maximum NUMBER of EDGES occur in a complete bipartite graph when every vertex has an edge to every opposite vertex in the graph. Number of edges in a complete bipartite graph is a*b, where a and b are no. of vertices on each side. This QUANTITY is maximum when a = b i.e. when there are 7 vertices on each side. So answer is 7 * 7 = 49.

The correct answer is (d) universal

For explanation I WOULD say: Any SET X may be used to generate the FREE semilattice FX. The free semilattice is DEFINED to consist of all of the finite subsets of X with the semilattice operation GIVEN by ordinary set union; the free semilattice has the universal property.

The correct ANSWER is (b) complete lattice

The explanation is: A poset is called a complete lattice if all its subsets have both a join and a MEET. EVERY complete lattice is a BOUNDED lattice.Every poset that is a complete semilattice must ALWAYS be a complete lattice.

Correct option is (c) x<=y<=z, where x, y in S implies z in S, for every element x, y, z in L

The explanation is: A SUBLATTICE S of a LATTICE L is a convex sublattice of L, if x ≤ z ≤ y and x, y in S implies that z belongs to S, for all elements x, y, z in L.

Correct CHOICE is (a) non-lattice poset

The best I can explain: The graph is an example of non-lattice poset where B and c have common UPPER bounds d, e and F but NONE of them is the least upper bound.

Right option is (d) bounded lattice

The best explanation: A lattice that has additionally a SUPREMUM element and an infimum element which SATISFY 0<=a<=1, for every an in the lattice is called a bounded lattice. A partially ORDERED set is a bounded lattice if and only if every finite set (including the EMPTY set) of elements has a JOIN and a meet.

The correct answer is (a) Join, meet

Easiest explanation: Join and meet are the binary operations reserved for lattices. The join of TWO ELEMENTS is their least upper bound. It is denoted by V, not to be confused with DISJUNCTION. The meet of two elements is their greatest LOWER bound. It is denoted by ∧ and not to be confused with a CONJUNCTION.

Correct option is (B) totally ordered poset

Easy explanation: A poset (P, <=) is known as totally ordered if EVERY TWO ELEMENTS of the poset are comparable. “<=” is CALLED a total order and a totally ordered set is also termed as a chain.

Correct option is (b) lattice

Explanation: A poset in which every PAIR of elements has both a LEAST upper bound and a GREATEST lower bound is called a lattice. A lattice can CONTAIN sublattices which are SUBSETS of that lattice.

The correct choice is (B) 2359296

Easy EXPLANATION: Here the total number of elements in S is 18 and so number of VERTICES in Hasse diagram are 2^18. Hence, the number of edges in Hasse diagram are 18 * 2^18-1=2359296.

The CORRECT option is (a) {V, x, y, z}

For explanation I would say: We know that, in a Hasse diagram, the maximal ELEMENT(s) are the top and the minimal ELEMENTS are at the bottom of the diagram. In the given poset, {v, x, y, z} is the maximal or greatest element and ∅ is the minimal or least element.

The correct answer is (a) reflexive, ANTISYMMETRIC and transitive

The explanation is: Let A is a set and ≤ is a RELATION on A, then ≤ is a PARTIAL order if it satisfies reflexive, antisymmetric, and transitive, i.e., for all x, y and z in P. That means, x ≤ x (REFLEXIVITY);

 if x ≤ y and y ≤ x then x = y (antisymmetry) and if x ≤ y and y ≤ z then x ≤ z (TRANSITIVITY).

Right CHOICE is (a) equal to(=)

The explanation: The identity RELATION = on any SET is a partial ORDER in which every two distinct elements are incomparable and that depicts the relation of both a partial order and an EQUIVALENCE relation. For non-linear orders, there are many advanced properties of posets.

Right choice is (a) NP-complete

Easy explanation: If the PARTIAL order has at most ONE minimal element, or it has at most one MAXIMAL element, then to test whether a partial order with multiple sources and SINKS can be drawn as a crossing-free Hasse DIAGRAM or not it’s time complexity is NP-complete.

Correct OPTION is (c) 13

To explain I would say: LET m be MIN degree and M be a max degree of a GRAPH, then m ≤ 2E/V ≤ M. Here, m=4, E=26, v=?

So, 4 ≤ (2*26)/V

V ≤ (52/4)

V ≤ 13 ⇒ V = 13.

Correct answer is (a) upward planar

To explain I would SAY: In a Hasse diagram if no two edges CROSS each other in the drawing of partial ORDER Hasse diagram, then its covering GRAPH CALLED the upward planar.

Correct choice is (B) 8

To explain: Vertices 1, 3, 5, 7 have DEGREE 8 and vertices 2, 4, 6, 8 have degree 7. By definition, sum of degree= 2 * No of edges

Let x = degree of vertex 8

8 + 7 + 8 + 7 + 8 + 7 + 8 + x =2 * 31

53 + x = 61

x = 8

Hence, degree of vertex 8 is 8.

Correct CHOICE is (a) even

Easy explanation: In any FINITE graph, sum of degree of all the vertices = 2 * number of edges.

Sum of degree of all the vertices with even degree + sum of degree of all the vertices with ODD degree = 2 * number of edges. Now, even number+ sum of degree of all the vertices with odd degree = even number. It is POSSIBLE if and only if number of odd degree vertices are even.

Right option is (C) 24

To explain: NUMBER of edges incident on a GRAPH is known as degree of a vertex. Sum of degrees of each vertex is called total degree of the graph. Total degree = 2 * number of vertices. So, if there are 24 vertices then total degree is 24.

The correct option is (d) no multiple edges, self-loops and parallel edges

Easiest EXPLANATION: If a graph say G = has no parallel or multiple edges and no self loops CONTAINED in it is CALLED a SIMPLE graph. An undirected graph may have multiple edges and self-loops.

The correct answer is (c) DISCONNECTED graphs

The BEST explanation: By the deletion of one EDGE from either connected or strongly connected graphs the graph obtained is termed as a disconnected graph. It can have connected components separated by the deletion of the edges. The edge that has to be deleted CALLED cut edge.

The correct answer is (d) connection of EVERY node with every other node INCLUDING itself in a digraph

The BEST explanation: Every node should be CONNECTED to every other node including itself in a digraph is the complete digraph. Now, graphs are connected, STRONGLY connected and disconnected

Correct answer is (a) A’ ⊂ A and R’ = R ∩ (A’ x A’)

The best explanation: A directed GRAPH or digraph is an ordered PAIR D where A(is a set of nodes of D) is a set and R(the ELEMENTS of R are the arcs of D) is a binary relation on A. The relation R is CALLED the incidence relation on D. Now, a digraph is a subgraph of D if i)A’ ⊂ A and ii)R’ = R ∩ (A’ x A’). If D’D, D’ is a PROPER subgraph of D.

The correct choice is (b) starting node and ending node are same

Easiest explanation: If the start node and end node are same in the PATH of a graph then it is termed as directed cycle i.e, c0 = CN. For instance, a C b a is a SIMPLE cycle in which start and end nodes are same(a). But, a c b b a is not a simple cycle as there is a LOOP .