I
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
6
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
45
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _______.
80
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n >= 2.
2
The number of edges in a 'n' vertex complete graph is ?
n * (n-1) / 2
How many diagonals can be drawn by joining the angular points of an octagon?
20
The number of different spanning trees in complete graph, K4 and bipartite graph, K2,2 have ______ and _______ respectively.
16,4
How many different trees are there with four nodes A, B, C and D ?
120
A given connected graph is a Euler Graph if and only if all vertices of are of
even degree
The number of distinct simple graphs with up to three nodes is
7
The number of edges in a regular graph of degree d and n vertices is
nd/2
Let X be the adjacency matrix of a graph G with no self loops. The entries along the principal diagonal of X are
all zeros
If a graph requires k different colours for its proper colouring, then the chromatic number of the graph is
k
A graph with n vertices and n-1 edges that is not a tree, is
Disconnected
If G is a graph with e edges and n vertices, the sum of the degrees of all vertices in G is
2e
In a graph G there is one and only one path between every pair of vertices then G is a
Tree
A graph in which all nodes are of equal degree, is known as
Regular graph
How many edges are there in a forest with v vertices and k components?
v − k
A cycle on n vertices is isomorphic to its complement. The value of n is _____.
5
The maximum number of edges in a bipartite graph on 12 vertices is __________________________.
36
Let G be the non-planar graph with the minimum possible number of edges. Then G has __________.
9 edges and 6 vertices
The minimum number of colours that is sufficient to vertex-colour any planar graph is _______________
4
What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?
19
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 _______________.
24
How many perfect matchings are there in a complete graph of 6 vertices ?
15