graph theory

Let $G(V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the numb...

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^{\pr...

Let $G(V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?

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

The diagram below shows a river system consisting of 7 segments, marked P, Q, R, S, T, U, and V. It splits the land into 5 zones, marked Z1, Z2, Z3, Z4, and Z5. We need to connect...

Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices, u and v, let d₁(u, v) and d₂(u, v) be the shortest distances...

Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following stateme...

Let G(V, E) be an undirected and unweighted graph with 100 vertices. Let d(u, v) denote the number of edges in a shortest path between vertices u and v in V. Let the maximum value...

The maximum value of x such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is __________. (answer in integer)

Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_1(u, v)$ and $d_2(u, v)$ be the sho...

Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following state...

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 _________

Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. W...

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

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

The number of distinct minimum-weight spanning trees of the following graph is _________

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is _________

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 _________

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

Let $$U = \{ 1,2,3\} $$. Let 2$$^U$$ denote the powerset of U. Consider an undirected graph G whose vertex set is 2$$^U$$. For any $$A,B \in {2^U},(A,B)$$ is an edge in G if and on...

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 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?

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

An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a...

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

Let G be a connected undirected weighted graph. Consider the following two statements. S 1 : There exists a minimum weight edge in G which is present in every minimum spanning tree...

Consider a graph G = (V, E), where V = {v 1 , v 2 , ...., v 100 }, E = {(v i , v j ) | 1 ≤ i < j ≤ 100}, and weight of the edge (v i , v j ) is |i - j|. The weight of the minimum s...

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

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

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

$$G = (V,E)$$ is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning...

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

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 = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For $$x \in V$$, let d(x) denote the shortest distance in G from s to x. A breadt...

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\}.$$ Th...

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 $$G = \left( {V,E} \right)$$ 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 con...

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

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

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry W ij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1...

Consider a complete undirected graph with vertex set {0,1,2,3,4}. Entry W ij in the matrix W below is the weight of the edge {i, j} $$$W = \left( {\matrix{ 0 & 1 & 8 & 1 & 4 \cr 1...

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

$$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$$?

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

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

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?

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 a weighted undirected graph with positive edge weights and let $$uv$$ be an edge in the graph. It is known that the shortest path from the source vertex $$s$$ to $$u$$ has...

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

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

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:

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

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

How many graphs on $$n$$ labeled vertices exist which have at least $$\left( {{n^2} - 3n} \right)/2\,\,\,$$ edges?

In a depth-first traversal of a graph G with n vertices,k edges are marked as tree edges. The number of connected components in G is

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

$$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\{ {{{\...

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

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 $$\,\,\,\,V = \left\{ {{v_1},\,\,{v_2},\,....,\,\,{v_n}} \right\}$$ of $$n$$ vertices?

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements...

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

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,