Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

The chromatic number of the following graph is _______.

G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ___________.

The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.

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

Let G be a graph with 100! vertices, with each vertex labeled by a distinct permutation of the numbers 1, 2, …, 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G.

Then, y + 10z = ___________.

In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?

A graph is self-complementary if it is isomorphic to its complement for all self-complementary graphs on n vertices, n is

Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?

An ordered -tuple (d₁, d₂, ..., d_n) with d₁ ≥ d₂ ≥ ... d_n is called graphic if there exists a simple undirected graph with n vertices having degrees d₁, d₂, ..., d_n respectively. Which of the following 6-tuples is NOT graphic?

The maximum number of edges in a bipartite graph on 12 vertices is ______.

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

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

Consider an undirected graph where self-loops are not allowed. The vertex set of G is {(i,j): 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c,d) if |a - c| ≤ 1 and |b - d| ≤ 1. The number of edges in this graph is __________.

A cycle on n vertices is isomorphic to its complement. The value of n is _____.

There are two elements x, y in a group (G,∗) such that every element in the group can be written as a product of some number of x's and y's in some order. It is known that

  x * x = y * y = x * y * x = y * x * y * x = e   

where e is the identity element. The maximum number of elements in such a group is ________.

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?

Which of the following statements is/are TRUE for undirected graphs?

P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.

The line graph L(G) of a simple graph G is defined as follows: · There is exactly one vertex v(e) in L(G) for each edge e in G. · For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e'are incident with the same vertex in G. Which of the following statements is/are TRUE?

(P) The line graph of a cycle is a cycle.
(Q) The line graph of a clique is a clique.
(R) The line graph of a planar graph is planar.
(S) The line graph of a tree is a tree.

Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to

K4 and Q3 are graphs with the following structures.

Which one of the following statement is TRUE  in relation to these graphs?

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

Which of the following statements is true for every planar graph on n vertices?

Which of the following graphs is isomorphic to

Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to

Let G = (V,E) be a graph. Define ξ(G) = Σd id x d, where id is the number of vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T),then

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?

(I) 7, 6, 5, 4, 4, 3, 2, 1
(II) 6, 6, 6, 6, 3, 3, 2, 2
(III) 7, 6, 6, 4, 4, 3, 2, 2
(IV) 8, 7, 7, 6, 4, 2, 1, 1

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

The 2ⁿ vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The number of vertices of degree zero in G is:

The 2ⁿ vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The number of connected components in G is:

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:

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

Which of the following graphs has an Eulerian circuit?

The 2ⁿ vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.

The maximum degree of a vertex in G is:

Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is

Which one of the following graphs is NOT planar?

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same colour, is

How many graphs on n labeled vertices exist which have at least (n² - 3n)/2 edges?

Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between

How many perfect matching are there in a complete graph of 6 vertices ?

A graph G = (V,E) satisfies |E|≤ 3|V|-6. The min-degree of G is defined as . Therefore, min-degree of G cannot be

The minimum number of colours required to colour the vertices of a cycle with η nodes in such a way that no two adjacent nodes have the same colour is

Maximum number of edges in a n-node undirected graph without self loops is

Let G₁ = (V,E₁) and G₂ = (V,E₂) be connected graphs on the same vertex set V with more than two vertices. If G₁ ∩ G₂ = (V, E₁ ∩ E₂) is not a connected graph, then the graph G₁ U G₂ = (V, E₁ U E₂)

How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v₁, v₂, ...,v_n} of n vertices?

Let S be a set of n elements {1, 2, …., n} and G a graph with 2ⁿ vertices, each vertex corresponding to a distinct subset of S. Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly 2 elements. Note: The symmetric difference of two sets R¹ and R² is defined as (R¹/R²)∪(R²/R¹)
(a) Every vertex in G has the same degree. What is the degree of a vertex in G?
(b) How many connected components does G have?

Let G be a connected, undirected graph. A cut in G is a set of edges whose removal results in 0 being broken into two or more components which are not connected with each other. The size of a cut is called its cardinality. A men-cut of G is a cut in G of minimum cardinality. Consider the following graph.

(a) Which of the following sets of edges is a cut?
(i) {(A,B), (E,F), (B,D), (A,E), (A,D)}
(ii) {(B,D), (C,F), (A,B)}

(b) What is the cardinality of a min-cut in the graph?

(c) Prove that if a connected undirected graph G with n vertices has a min-cut of cardinality K, then G has atleast (nk/2) edges.

(a) Prove by induction that the expression for the number of diagonals in a polygon of n sides is n(n-3)/2.

(b) Let R be a binary relation on A = {a, b, c, d, e, f, g, h} represented by following two component digraph. Find the smallest integers m and n such that mm = Rⁿ.

Let (A, *) be a semi group. Furthermore, for every a and b in A, if a ≠ b, then a*b ≠ b*a.

(a) Show that for every a in A

 a*a = a 

(b) Show that for every a, b in A

 a*b*a = a  

(c) Show that for every a, b, c in A

 a*b*c = a*c 

Let G be a graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if |i - j| = 8 or |i - j| = 12. The number of connected components in G is

The minimum number of edges in a connected cyclic graph on n vertices is:

Prove that in finite graph, the number of vertices of odd degree is always even.

The number of distinct simple graphs with upto three nodes is

The number of edges in a regular graph of degree d and n vertices is _________.

Maximum number of edges in a planar graph with n vertices is ________

A non-planar graph with minimum number of vertices has

Let T be a Depth First Tree of a undirected graph G. An array P indexed by vertices of G is given. P[V] is the parent of vertex V, in T. Parent of the root is the root itself.

Give a method for finding and printing the cycle formed if the edge (u,v) of G not in T (i.e., e ∈ G − T) is now added to T.

Time taken by your method must be proportional to the length of the cycle.

Describe the algorithm in a PASCAL – like language. Assume that the variables have been suitably declared.

Graph G is obtained by adding vertex s to K_3,4 and making s adjacent to every vertex of K_3,4. The minimum number of colours required to edge-colour G is _____.

(a) If G is a group of even order, then show that there exists an element a ≠ e, the identity in g, such that a² = e

(b) Consider the set of integers {1,2,3, 4,6,8,12,24} together with the two binary operations LCM (lowest common multiple) and GCD (greatest common divisor). Which of the following algebraic structures does this represent?

 (i) group            (ii) ring
 (iii) field          (iv) lattice  

The maximum number of possible edges in an undirected graph with a vertices and k components is ________.

Choose the correct alternatives (More than one may be correct).

Which of the following graphs is/are planner?