search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Recent questions and answers in Graph Theory

34 votes
9 answers
1
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. $2$ $3$ $n-1$ $n$
answered Jul 19 in Graph Theory Chirag Shilwant 4.5k views
3 votes
2 answers
2
Consider directed graphs on $n$ labelled vertices $\{1,2, \dots ,n\}$, where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loops. How many graphs have exactly two cycles ? $\sum_{k=1}^{n-1} k!(n-k)!$ $\frac{n!}{2}\bigg[\sum_{k=1}^{n-1} \frac{1}{k(n-k)}\bigg]$ $n!\bigg[\sum_{k=1}^{n-1} \frac{1}{k}\bigg]$ $\frac{n!(n-1)}{2}$ None of the above
answered Jul 14 in Graph Theory vaibhavkedia968 556 views
25 votes
8 answers
3
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Hamiltonian cycle grid hypercube tree
answered Jul 14 in Graph Theory vaibhavkedia968 2.6k views
0 votes
1 answer
4
The number of labelled subgraph possible for the graph given below are ________.
answered Jun 11 in Graph Theory krishx18 121 views
27 votes
6 answers
5
2 votes
2 answers
6
Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$—that is, a sequence of $k+1$ distinct vertices $v_0, v_1, \dots , v_k$ such that for $0 \leq i < k,$ $v_i$ is connected to $v_{i+1}$ in $G$.
answered May 15 in Graph Theory Falahamin 208 views
1 vote
2 answers
7
A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that: Each road connects exactly two buildings. Any two buildings are connected via a sequence of roads. Omitting any road leads to at ... . Is it always possible to colour each building with either red or blue so that every road connects a red and blue building?
answered May 14 in Graph Theory Falahamin 177 views
0 votes
1 answer
8
In a given following graph among the following sequences: abeghf abfehg abfhge afghbe Which are depth first traversals of the above graph? I,II and IV only I and IV only II,III and IV only I,III and IV only
answered May 10 in Graph Theory Mohit Kumar 6 62 views
0 votes
1 answer
9
Which of the following statements is/are TRUE? $S1$:The existence of an Euler circuit implies that an Euler path exists. $S2$:The existence of an Euler path implies that an Euler circuit exists. $S1$ is true. $S2$ is true. $S1$ and $S2$ both are true. $S1$ and $S2$ both are false.
answered May 10 in Graph Theory Mohit Kumar 6 55 views
0 votes
1 answer
10
Considering the following graph, which one of the following set of edged represents all the bridges of the given graph? $(a,b), (e,f)$ $(a,b), (a,c)$ $(c,d), (d,h)$ $(a,b)$
answered May 10 in Graph Theory Mohit Kumar 6 52 views
0 votes
1 answer
11
Weighted graph : Is a bi-directional graph Is directed graph Is graph in which number associated with arc Eliminates table method
answered May 5 in Graph Theory Mohit Kumar 6 39 views
0 votes
1 answer
12
What are the appropriate data structures for graph traversal using Breadth First Search(BFS) and Depth First Search(DFS) algorithms? Stack for BFS and Queue for DFS Queue for BFS and Stack for DFS Stack for BFS and Stack for DFS Queue for BFS and Queue for DFS
answered May 2 in Graph Theory abhishek tiwary 51 views
0 votes
1 answer
13
0 votes
3 answers
14
0 votes
7 answers
15
0 votes
3 answers
16
The following graph has no Euler circuit because It has $7$ vertices. It is even-valent (all vertices have even valence). It is not connected. It does not have a Euler circuit.
answered Apr 3 in Graph Theory smsubham 127 views
0 votes
3 answers
17
0 votes
1 answer
18
Which of the following statements is/are TRUE for an undirected graph? Number of odd degree vertices is even Sum of degrees of all vertices is even P only Q only Both P and Q Neither P nor Q
answered Apr 3 in Graph Theory immanujs 61 views
0 votes
1 answer
19
A connected planar graph divides the plane into a number of regions. If the graph has eight vertices and these are linked by $13$ edges, then the number of regions is: $5$ $6$ $7$ $8$
answered Apr 3 in Graph Theory immanujs 46 views
0 votes
2 answers
20
The number of edges in a complete graph with $N$ vertices is equal to : $N (N−1)$ $2N−1$ $N−1$ $N(N−1)/2$
answered Apr 2 in Graph Theory immanujs 71 views
0 votes
1 answer
21
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: $3$ $4$ $5$ $6$
answered Apr 1 in Graph Theory smsubham 53 views
0 votes
1 answer
22
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is $E$ $2E$ $V$ $2V$
asked Mar 30 in Graph Theory Lakshman Patel RJIT 157 views
0 votes
0 answers
23
Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? In adjacency list representation, space is saved for sparse graphs. Deleting a vertex in adjacency list representation is easier than ... matrix representation. Adding a vertex in adjacency list representation is easier than adjacency matrix representation. All of the option.
asked Mar 30 in Graph Theory Lakshman Patel RJIT 69 views
0 votes
1 answer
24
A path in graph $G$, which contains every vertex of $G$ and only once? Euler circuit Hamiltonian path Euler Path Hamiltonian Circuit
asked Mar 30 in Graph Theory Lakshman Patel RJIT 65 views
0 votes
2 answers
25
Choose the most appropriate definition of plane graph. A simple graph which is isomorphic to hamiltonian graph. A graph drawn in a plane in such a way that if the vertex set of graph can be partitioned into two non-empty disjoint subset $X$ and $Y$ in such a way that each edge ... . A graph drawn in a plane in such a way that any pair of edges meet only at their end vertices. None of the option.
asked Mar 30 in Graph Theory Lakshman Patel RJIT 127 views
0 votes
1 answer
26
Let $G$ be a complete undirected graph on $8$ vertices. If vertices of $G$ are labelled, then the number of distinct cycles of length $5$ in $G$ is equal to: $15$ $30$ $56$ $60$
asked Mar 30 in Graph Theory Lakshman Patel RJIT 93 views
0 votes
3 answers
27
Let $G$ be a simple undirected graph on $n=3x$ vertices $(x \geq 1)$ with chromatic number $3$, then maximum number of edges in $G$ is $n(n-1)/2$ $n^{n-2}$ $nx$ $n$
asked Mar 30 in Graph Theory Lakshman Patel RJIT 184 views
0 votes
1 answer
28
The number of edges in a complete graph with $‘n’$ vertices is equal to : $n(n-1)$ $\large\frac{n(n-1)}{2}$ $n^2$ $2n-1$
answered Mar 29 in Graph Theory chirudeepnamini 58 views
0 votes
1 answer
29
The following lists are the degrees of all the vertices of a graph : $1,2,3,4,5$ $3,4,5,6,7$ $1, 4, 5, 8, 6$ $3,4,5,6$ (i) and (ii) (iii) and (iv) (iii) and (ii) (ii) and (iv)
answered Mar 27 in Graph Theory Divya Devi 50 views
0 votes
1 answer
30
Consider a Hamiltonian Graph $G$ with no loops or parallel edges and with $\left | V\left ( G \right ) \right |= n\geq 3$. The which of the following is true? $\text{deg}\left ( v \right )\geq \frac{n}{2}$ for each vertex $v\\$ ... $v$ and $w$ are not connected by an edge All of the above
asked Mar 24 in Graph Theory jothee 81 views
14 votes
6 answers
31
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimum-weight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II
answered Mar 17 in Graph Theory immanujs 5.8k views
28 votes
3 answers
32
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$
answered Mar 7 in Graph Theory vivekgatecs2020 3.7k views
33 votes
4 answers
33
Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices have the same degree. At least three vertices have the same degree. All vertices have the same degree.
answered Mar 7 in Graph Theory vivekgatecs2020 3.4k views
6 votes
3 answers
35
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 _______
answered Feb 27 in Graph Theory immanujs 1.6k views
10 votes
3 answers
36
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: $6$ $8$ $9$ $13$
answered Feb 21 in Graph Theory Pratyush Priyam Kuan 2k views
31 votes
5 answers
37
29 votes
5 answers
38
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 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: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$
answered Feb 20 in Graph Theory Pratyush Priyam Kuan 3.3k views
24 votes
2 answers
39
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: $12$ $8$ less than $8$ more than $12$
answered Feb 20 in Graph Theory Pratyush Priyam Kuan 3.4k views
18 votes
5 answers
40
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n-1$ $n$ $n+1$ $2n-1$
answered Feb 20 in Graph Theory Pratyush Priyam Kuan 2.4k views
To see more, click for all the questions in this category.
...