Graph Theory

Let $G$ be an undirected graph, which is a path on 8 vertices. The number of matchings in $G$ is $\_\_\_\_$ (answer in integer)

Consider a complete graph $K_n$ with $n$ vertices ( $n>4$ ). Note that multiple spanning trees can be constructed over $K_n$. Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between...

Let $G(V, E)$ be a simple, undirected graph. A vertex cover of $G$ is a subset $V^{\prime} \subseteq V$ such that for every $(u, v) \in E, u \in V^{\prime \prime}$ or $v \in V^{\prime}$. Let the size of the smallest vert...

Consider a knock-out women's badminton singles tournament where there are no ties. The loser in each game is eliminated from the tournament. Every player plays until she is defeated or remains the last undefeated player....

An undirected, unweighted, simple graph $G(V, E)$ is said to be 2 -colorable if there exists a function $c: V \rightarrow\{0,1\}$ such that for every $(u, v) \in E, c(u) \neq c(v)$. Which of the following statements abou...

Let A be the adjacency matrix of a simple undirected graph G. Suppose A is its own inverse. Which one of the following statements is always TRUE?

Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in G has even weight. Which of the following statements is/are TRUE for every such graph G ?

Let $A$ be the adjacency matrix of a simple undirected graph $G$. Suppose $A$ is its own inverse. Which one of the following statements is always TRUE?

The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is __________

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$. Which of the following statements is/are always T...

The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected components in G is ________

Let G be a simple, finite, undirected graph with vertex set {$$v_1,...,v_n$$}. Let $$\Delta(G)$$ denote the maximum degree of G and let N = {1, 2, ...} denote the set of all possible colors. Color the vertices of G using...

Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is __________.

Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

Let G(V, E) be a directed graph, where V = {1, 2, 3, 4, 5} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A. $$A[i][j] = \left\{ {\matrix{ {1,} & {1 \le j \le i \l...

In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______

Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as: diam(G) = $$\displaystyle\max_{u, x\in V}$$ {the length of shortest path between u and v} Let M be the adjacency matrix of G. D...

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

Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a unique minimum spanning tree, if, for every cut of G , there is a unique...

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

Let $$G$$ be a graph with $$100!$$ vertices, with each vertex labelled 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...

$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 _____________ .

Consider a set $$U$$ of $$23$$ different compounds in a Chemistry lab. There is a subset $$S$$ of $$U$$ of $$9$$ compounds, each of which reacts with exactly $$3$$ compounds of $$U.$$ Consider the following statements: $...

Let $$G$$ be a connected undirected graph of $$100$$ vertices and $$300$$ edges. The weight of a minimum spanning tree of $$G$$ is $$500.$$ When the weight of each edge of $$G$$ is increased by five, the weight of a mini...

In a connected graph, 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 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 ___________.

Consider an undirectional graph $$G$$ where self-loops are not allowed. The vertex set of $$G$$ is $$\left\{ {\left( {i,j} \right):\,1 \le i \le 12,\,1 \le j \le 12} \right\}.$$ There is an edge between $$(a,b)$$ and $$(...

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?

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?

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

An ordered $$n$$-tuple $$\left( {{d_1},\,\,{d_2},\,....,{d_n}} \right)$$ with $${{d_1} \ge ,\,\,{d_2} \ge .... \ge {d_n}}$$ is called graphic if there exists a simple undirected graph with $$n$$ vertices having degrees $...

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$$,...

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.

Let G be a simple undirected planner 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$$ $$\,\,\,\,\, = \,\,\,\left( {V,\,\,\,\,\,E} \right)$$ be a graph. Define $$\xi \left( G \right) = \sum\limits_d {{i_d} \times } {\mkern 1mu} d,$$ where $${{i_d}}$$ is the number of vertices of degree $$d$$ in $...

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? $${\rm I}.$$$$\,\,\,\,\,7,...

What is the chromatic number of an $$n$$-vertex simple connected graph which does not contain any odd length cycle? Assume $$n \ge 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 edge-disjoint spanning trees. Which of the following in NOT true for $$G$$?

A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbours. Starting with the above tree, whil...

$$G$$ is a simple undirected graph. Some vertices of $$G$$ are of odd degree. Add a node $$v$$ to $$G$$ and make it adjacent to each odd degree vertex of $$G$$. The resultant graph is sure to be

What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?

A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbours. $${n_3}$$ can be expressed as:

A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of...

Which of the following graphs has an Eulerian circuit?

The maximum number of binary trees that can be formed with three unlabeled nodes is:

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

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

Consider the undirected graph $$G$$ defined as follows. The vertices of $$G$$ are bit strings of length $$n$$. We have an edge between vertex $$u$$ and vertex $$v$$ if and only if $$u$$ and $$v$$ differ in exactly one bi...

Consider a weighted complete graph $$G$$ on the vertex set $$\left\{ {{v_1},\,\,\,{v_2},....,\,\,\,{v_n}} \right\}$$ such that the weight of the edge $$\left( {{v_i},\,\,\,\,{v_j}} \right)$$ is $$2\left| {i - j} \right|$...

The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices of $$G$$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The m...

If all the edge weights of an undirected graph are positive, then any subject of edges that connects all the vertices and has minimum total weight is a

The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices of $$G$$ are adjacent if and only if the corresponding sets intersect in exactly two elements. the n...

Let $$G$$ be the 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:

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:

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?

Let $${G_1} = \left( {V,\,{E_1}} \right)$$ and $${G_2} = \left( {V,\,{E_2}} \right)$$ be connected graphs on the same vertex set $$V$$ with more than two vertices. If $${G_1} \cap {G_2} = \left( {V,{E_1} \cap {E_2}} \rig...

What is the maximum number of edges in an acyclic undirected graph with $$n$$ vertices?

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

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

$$A$$ graph $$G$$ $$=$$ $$(V, E)$$ satisfies $$\left| E \right| \le \,3\left| V \right| - 6.$$ The min-degree of $$G$$ is defined as $$\mathop {\min }\limits_{v \in V} \left\{ {{{\mathop{\rm d}\nolimits} ^ \circ }egree\l...

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

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

The minimum number of colors required to color the vertices of a cycle with $$n$$ nodes in such a way that no two adjacent nodes have the same colour is:

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

how many undirected graphs (not necessarily connected) can be constructed out of a given $$\,\,\,\,V = \left\{ {{v_1},\,\,{v_2},\,....,\,\,{v_n}} \right\}$$ of $$n$$ vertices?

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

The number of distinct simple graph with upto three nodes is

Maximum number of edges in a planar graph with $$n$$ vertices is _______ .

A non-planar graph with minimum number of vertices has

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

A graph is planar if and only if,