menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
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 Posts
IIT Madras MS in CSE Interview Experience
My GATE Preparation Experience (GATE CS 2020 AIR 188)
Interview Experience at IITM MS CS 2020
IIT Delhi CSE MS(R) Interview Experience- July 2020
Direct PhD Interview Experience IIT Madras (July 2020)
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.3k)
Discrete Mathematics
(5.9k)
Mathematical Logic
(2.1k)
Set Theory & Algebra
(1.5k)
Combinatory
(1.4k)
Graph Theory
(844)
Probability
(1k)
Linear Algebra
(732)
Calculus
(600)
Digital Logic
(3k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.5k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.4k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions and answers in Graph Theory
Recent Blog Comments
I think that's a matter of personal preference...
Bro in your text you din't mention about your...
I mentioned 2 of them in the blog. I joined one...
What are all the test series you joined and from...
They wont be closed before GATE 2021. But it is...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Recent questions and answers in Graph Theory
34
votes
9
answers
1
GATE2009-2
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$
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
gate2009
graph-theory
graph-coloring
normal
3
votes
2
answers
2
TIFR2019-B-15
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
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
tifr2019
graph-connectivity
graph-theory
25
votes
8
answers
3
GATE2006-IT-11
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
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
gate2006-it
graph-theory
graph-connectivity
normal
0
votes
1
answer
4
Made Easy Practice Book
The number of labelled subgraph possible for the graph given below are ________.
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
GATE2014-2-3
The maximum number of edges in a bipartite graph on $12$ vertices is____
The maximum number of edges in a bipartite graph on $12$ vertices is____
answered
May 29
in
Graph Theory
Aalok8523
7.2k
views
gate2014-2
graph-theory
graph-connectivity
numerical-answers
normal
2
votes
2
answers
6
CMI2010-B-02
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$.
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
cmi2010
descriptive
graph-theory
graph-connectivity
1
vote
2
answers
7
CMI2011-B-01a
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 ... it always possible to colour each building with either red or blue so that every road connects a red and blue building?
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
cmi2011
descriptive
graph-coloring
0
votes
1
answer
8
NIELIT 2017 July Scientist B (IT) - Section B: 5
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
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
nielit2017july-scientistb-it
0
votes
1
answer
9
NIELIT 2017 July Scientist B (IT) - Section B: 7
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.
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
nielit2017july-scientistb-it
0
votes
1
answer
10
NIELIT 2017 July Scientist B (IT) - Section B: 6
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)$
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
nielit2017july-scientistb-it
0
votes
1
answer
11
UGCNET-Dec2004-II: 23
Weighted graph : Is a bi-directional graph Is directed graph Is graph in which number associated with arc Eliminates table method
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
ugcnetdec2004ii
0
votes
1
answer
12
NIELIT 2017 July Scientist B (IT) - Section B: 4
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
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
nielit2017july-scientistb-it
0
votes
1
answer
13
NIELIT 2016 MAR Scientist B - Section B: 3
Maximum degree of any node in a simple graph with $n$ vertices is $n-1$ $n$ $n/2$ $n-2$
Maximum degree of any node in a simple graph with $n$ vertices is $n-1$ $n$ $n/2$ $n-2$
answered
May 2
in
Graph Theory
abhishek tiwary
68
views
nielit2016mar-scientistb
0
votes
3
answers
14
NIELIT 2017 July Scientist B (CS) - Section B: 14
If $G$ is an undirected planar graph on $n$ vertices with $e$ edges then $e\leq n$ $e\leq 2n$ $e\leq 3n$ None of the option
If $G$ is an undirected planar graph on $n$ vertices with $e$ edges then $e\leq n$ $e\leq 2n$ $e\leq 3n$ None of the option
answered
May 2
in
Graph Theory
abhishek tiwary
183
views
nielit2017july-scientistb-cs
0
votes
7
answers
15
NIELIT 2017 July Scientist B (CS) - Section B: 13
For the graph shown, which of the following paths is a Hamilton circuit? $ABCDCFDEFAEA$ $AEDCBAF$ $AEFDCBA$ $AFCDEBA$
For the graph shown, which of the following paths is a Hamilton circuit? $ABCDCFDEFAEA$ $AEDCBAF$ $AEFDCBA$ $AFCDEBA$
answered
May 2
in
Graph Theory
abhishek tiwary
154
views
nielit2017july-scientistb-cs
0
votes
3
answers
16
NIELIT 2017 July Scientist B (CS) - Section B: 12
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.
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
nielit2017july-scientistb-cs
0
votes
3
answers
17
NIELIT 2017 July Scientist B (CS) - Section B: 11
Consider the following graph $L$ and find the bridges,if any. No bridge $\{d,e\}$ $\{c,d\}$ $\{c,d\}$ and $\{c,f\}$
Consider the following graph $L$ and find the bridges,if any. No bridge $\{d,e\}$ $\{c,d\}$ $\{c,d\}$ and $\{c,f\}$
answered
Apr 3
in
Graph Theory
smsubham
66
views
nielit2017july-scientistb-cs
0
votes
1
answer
18
NIELIT 2017 July Scientist B (CS) - Section B: 2
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
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
nielit2017july-scientistb-cs
0
votes
1
answer
19
NIELIT 2017 July Scientist B (IT) - Section B: 8
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$
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
nielit2017july-scientistb-it
0
votes
2
answers
20
UGCNET-Dec2006-II: 3
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$
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
ugcnetdec2006ii
0
votes
1
answer
21
NIELIT 2016 DEC Scientist B (CS) - Section B: 5
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$
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
nielit2016dec-scientistb-cs
0
votes
1
answer
22
NIELIT 2017 July Scientist B (IT) - Section B: 1
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is $E$ $2E$ $V$ $2V$
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
nielit2017july-scientistb-it
0
votes
0
answers
23
NIELIT 2017 July Scientist B (IT) - Section B: 2
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 ... Adding a vertex in adjacency list representation is easier than adjacency matrix representation. All of the option.
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
nielit2017july-scientistb-it
0
votes
1
answer
24
NIELIT 2017 July Scientist B (IT) - Section B: 3
A path in graph $G$, which contains every vertex of $G$ and only once? Euler circuit Hamiltonian path Euler Path Hamiltonian Circuit
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
nielit2017july-scientistb-it
0
votes
2
answers
25
NIELIT 2017 July Scientist B (CS) - Section B: 15
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 ... in a plane in such a way that any pair of edges meet only at their end vertices. None of the option.
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
nielit2017july-scientistb-cs
0
votes
1
answer
26
NIELIT 2017 DEC Scientist B - Section B: 23
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$
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
nielit2017dec-scientistb
graph-theory
cycle
0
votes
3
answers
27
NIELIT 2017 DEC Scientist B - Section B: 52
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$
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
nielit2017dec-scientistb
graph-theory
graph-coloring
0
votes
1
answer
28
UGCNET-Dec2007-II: 2
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$
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
ugcnetdec2007ii
0
votes
1
answer
29
UGCNET-Dec2004-II: 4
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)
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
ugcnetdec2004ii
0
votes
1
answer
30
UGCNET-Jan2017-II: 5
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
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
ugcnetjan2017ii
graph-theory
graph-coloring
14
votes
6
answers
31
GATE2019-38
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
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
gate2019
engineering-mathematics
discrete-mathematics
graph-theory
graph-connectivity
28
votes
3
answers
32
GATE2002-1.4
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$
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
gate2002
graph-theory
graph-coloring
normal
33
votes
4
answers
33
GATE2009-3
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.
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
gate2009
graph-theory
normal
degree-of-graph
2
votes
2
answers
34
Zeal Test Series 2019: Graph Theory - Graph Coloring
what is index ?
what is index ?
answered
Mar 2
in
Graph Theory
Parth Narodia
239
views
zeal
graph-theory
graph-coloring
zeal2019
6
votes
3
answers
35
GATE2020-CS-52
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 _______
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
gate2020-cs
numerical-answers
grab
graph-theory
10
votes
3
answers
36
GATE2005-10
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$
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
gate2005
graph-theory
graph-planarity
31
votes
5
answers
37
GATE2002-1.25, ISRO2008-30, ISRO2016-6
The maximum number of edges in a n-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$
The maximum number of edges in a n-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$
answered
Feb 20
in
Graph Theory
Pratyush Priyam Kuan
6.4k
views
gate2002
graph-theory
easy
isro2008
isro2016
graph-connectivity
29
votes
5
answers
38
GATE2006-73
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}$
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
gate2006
graph-theory
normal
graph-connectivity
24
votes
2
answers
39
GATE2005-11
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$
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
gate2005
graph-theory
normal
graph-connectivity
18
votes
5
answers
40
GATE2004-IT-5
What is the maximum number of edges in an acyclic undirected graph with $n$ vertices? $n-1$ $n$ $n+1$ $2n-1$
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
gate2004-it
graph-theory
graph-connectivity
normal
To see more, click for all the
questions in this category
.
...