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.
1 Crore+ students have signed up on EduRev. Have you? Download the App 
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
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
What is the chromatic number of an nvertex simple connected graph which does not contain any odd length cycle? Assume n >= 2.
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
Which of the following statements is true for every planar graph on n vertices?
G is a graph on n vertices and 2n  2 edges. The edges of G can be partitioned into two edgedisjoint spanning trees. Which of the following is NOT true for G?
Let G be the nonplanar graph with the minimum possible number of edges. Then G has
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 ?
Consider an undirected graph G where selfloops 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 __________.
An ordered ntuple (d1, d2, … , dn) with d1 >= d2 >= ⋯ >= dn is called graphic if there exists a simple undirected graph with n vertices having degrees d1, d2, … , dn respectively. Which of the following 6tuples is NOT graphic?
The maximum number of edges in a bipartite graph on 12 vertices is
A cycle on n vertices is isomorphic to its complement. The value of n is _____
55 docs215 tests

55 docs215 tests
