Recent questions tagged graph-theory / GATE Overflow for GATE CSE

3 votes

4 answers

781

subgraphs
number of subgraph for K3 is

number of subgraph for K3 is

Pooja Palod

1.4k views

Pooja Palod asked Jan 24, 2016

1 votes

1 answer

782

Ace Test Series: Graph Theory - Graph Connectivity
I think the explanation is for edges for which graph is always connected.

I think the explanation is for edges for which graph is always connected.

Tushar Shinde

537 views

Tushar Shinde asked Jan 24, 2016

1 votes

2 answers

783

Max Number of edges
A simple undirected graph ‘X’ has 10 vertices. If ‘X’ has 5 equally sized connected components, the maximum number of edges in graph ‘X’ is _________.

A simple undirected graph ‘X’ has 10 vertices. If ‘X’ has 5 equally sized connected components, the maximum number of edges in graph ‘X’ is _________.

Akanksha Kesarwani

2.9k views

Akanksha Kesarwani asked Jan 22, 2016

7 votes

2 answers

784

Finding matching number of graph
Given explanation: In the above explanation, it is written that matching number is 4 but I am getting matching number as 3 for this graph(choosing edges 1-2, 3-4 and 6-7). Please check where I am going wrong

Given explanation:In the above explanation, it is written that matching number is 4 but I am getting matching number as 3 for this graph(choosing edges 1-2, 3-4 and 6-7)....

shikharV

2.3k views

shikharV asked Jan 18, 2016

3 votes

2 answers

785

Counting number of articulation points
Given answer is 2, I think it should be 3: F,A, and G are articulation points. Please check

Given answer is 2, I think it should be 3: F,A, and G are articulation points. Please check

shikharV

1.2k views

shikharV asked Jan 15, 2016

2 votes

1 answer

786

Question on graphs
Given explanation: I couldn't understand why S1 is false. Please explain

Given explanation:I couldn't understand why S1 is false. Please explain

shikharV

485 views

shikharV asked Jan 14, 2016

3 votes

3 answers

787

Ace Test Series: Graph Theory - Degree Of Graph
How to PROVE S2 is correct?? Consider the statements $S_1$ ) In any simple graph with more than one vertex, there must exist at-least $2$ vetices of the same degree $S_2$ ) A graph with $13$ vertices, $31$ edges, $3$ vertices of degree $5$ and $7$ ... $S_2$ is false C). $S_1$ is false and $S_2$ is true D). Both $S_1$ and $S_2$ are true

How to PROVE S2 is correct??Consider the statements $S_1$ ) In any simple graph with more than one vertex, there must exist at-least $2$ vetices of the same degree $...

Tushar Shinde

1.3k views

Tushar Shinde asked Jan 13, 2016

1 votes

3 answers

788

Find maximum edges in Graph

Himanshu1

594 views

Himanshu1 asked Jan 6, 2016

0 votes

1 answer

789

check the question
k5 : the regular graph of degree 4 L(k5) : the line graph of graph k5 1. the line graph L(k5) is a regular graph of degree_______ and edges ________

k5 : the regular graph of degree 4L(k5) : the line graph of graph k51. the line graph L(k5) is a regular graph of degree_______ and edges ________

pritika kundu

700 views

pritika kundu asked Jan 5, 2016

0 votes

1 answer

790

Question on graph theory
Please explain how did they get that equation in E and V.

Please explain how did they get that equation in E and V.

shikharV

642 views

shikharV asked Jan 4, 2016

4 votes

1 answer

791

How many strongly connected component are there in the above graph
Consider the following graph (G): How many strongly connected components are there in the above graph?

Consider the following graph (G):How many strongly connected components are there in the above graph?

worst_engineer

9.2k views

worst_engineer asked Dec 29, 2015

1 votes

2 answers

792

group theory
Which of the following is not a group? Set of integer under multiplication operation. Set of natural number under multiplication. Set of natural number under addition. All of the above Why is it not group under addition? Ans given is d.

Which of the following is not a group?Set of integer under multiplication operation.Set of natural number under multiplication.Set of natural number under addition.All of...

UK

1.8k views

UK asked Dec 27, 2015

4 votes

1 answer

793

Graph theory
If a simple graph has 3 component and these component have 4,5,6 vertices ,then maximum number of edge present in graph. (a) 26 (b) 76 (c)30 (d)42

If a simple graph has 3 component and these component have 4,5,6 vertices ,then maximum number of edge present in graph.(a) 26(b) 76(c)30(d)42

ManojK

1.5k views

ManojK asked Dec 26, 2015

2 votes

1 answer

794

Graph theory
How many non isomorphic directed simple graph are there with n vertices?

How many non isomorphic directed simple graph are there with n vertices?

ManojK

1.5k views

ManojK asked Dec 26, 2015

0 votes

1 answer

795

graph theory
How many non-isomorphic simple graph are there with 5 vertices and 3 edges?how to approach this qus....

How many non-isomorphic simple graph are there with 5 vertices and 3 edges?how to approach this qus....

ManojK

416 views

ManojK asked Dec 26, 2015

2 votes

1 answer

796

how to find path of length 3 in below graph including V5 ?
what is the issue in the given approach ? Since the path should pass through v5 I am assuming we only include the path in which v5 can be intermediate vertex. And path visited in reverse order is not counted as distinct. Let us ... first vertex we can have total of 16 choices. This gives total paths possible as 16. But answer given is 4C3 .

what is the issue in the given approach ?Since the path should pass through v5 I am assuming we only include the path in which v5 can be intermediate vertex.And path visi...

radha gogia

1.5k views

radha gogia asked Dec 21, 2015

0 votes

2 answers

797

graph theory

nitish

582 views

nitish asked Dec 20, 2015

3 votes

3 answers

798

Number of nodes of distinct degree
In a simple connected undirected graph with n nodes(where n≧2), The maximum number of nodes with distinct degrees is n-1 n-2 n-3 2

In a simple connected undirected graph with n nodes(where n≧2), The maximum number of nodes with distinct degrees is n-1n-2n-32

sharma.abhilasha

3.0k views

sharma.abhilasha asked Dec 15, 2015

5 votes

2 answers

799

TIFR CSE 2015 | Part B | Question: 13
Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for all $u, v \in V_{1}, (u, v) \in E_{1}$ ... $L$ is $NP$- hard. $L$ is undecidable. Only $(i)$ Only $(ii)$ Only $(iii)$ $(i)$ and $(ii)$ $(ii)$ and $(iii)$

Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for...

makhdoom ghaya

1.0k views

makhdoom ghaya asked Dec 8, 2015

20 votes

2 answers

800

TIFR CSE 2015 | Part B | Question: 11
Let $K_{n}$ be the complete graph on $n$ vertices labeled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n - 1)}{2}$ edges. What is the number of spanning trees of $K_{n}$? $\frac{m}{n - 1}$ $m^{n - 1}$ $n^{n - 2}$ $n^{n - 1}$ None of the above

Let $K_{n}$ be the complete graph on $n$ vertices labeled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n - 1)}{2}$ edges. What is the number of spanning trees of $K_{n...

makhdoom ghaya

2.2k views

makhdoom ghaya asked Dec 8, 2015

28 votes

7 answers

801

TIFR CSE 2015 | Part B | Question: 5
Suppose $\begin{pmatrix} 0&1 &0&0&0&1 \\ 1&0&1&0&0&0 \\ 0&1&0&1&0&1 \\ 0&0&1&0&1&0 \\ 0&0&0&1&0&1 \\ 1&0&1&0&1&0 \end{pmatrix}$ is the adjacency ... the above adjacency matrix? Only $(i)$ Only $(ii)$ Only $(iii)$ Only $(iv)$ $(i)$ and $(ii)$

Suppose $\begin{pmatrix}0&1 &0&0&0&1 \\1&0&1&0&0&0 \\0&1&0&1&0&1 \\0&0&1&0&1&0 \\0&0&0&1&0&1 \\1&0&1&0&1&0\end{pmatrix}$is the adjacency matrix of an undirected graph...

makhdoom ghaya

4.4k views

makhdoom ghaya asked Dec 7, 2015

2 votes

1 answer

802

Given no of vertex & edges how to find no of Non Isomorphic graphs possible ?
Assume that ‘e’ is the number of edges and n is the number of vertices. The number of non-isomorphic graphs possible with n-vertices such that graph is 3-regular graph and e = 2n – 3 are ... ? , this is real question ! Is there any algorithm for this ? From Made Easy FLT 6-Practice Test 14

Assume that ‘e’ is the number of edges and n is the number of vertices. The number of non-isomorphic graphs possible with n-vertices such that graph is 3-regu...

Akash Kanase

2.3k views

Akash Kanase asked Dec 1, 2015

6 votes

3 answers

803

How to find no of paths of length 2 in the below graph ?
Determine the number of paths of length $2$ in the following graph I couldn't get this logic .

Determine the number of paths of length $2$ in the following graphI couldn't get this logic .

radha gogia

5.0k views

radha gogia asked Nov 28, 2015

1 votes

1 answer

804

Rosen 8.2.54.
If G is a simple graph with 15 edges and $\bar{G}$ has 13 edges, how many vertices does G have?

If G is a simple graph with 15 edges and $\bar{G}$ has 13 edges, how many vertices does G have?

Hira Thakur

4.5k views

Hira Thakur asked Nov 21, 2015

1 votes

1 answer

805

Relation between graphs
Is there is any relation between bipartite graph, complete bipartite and planar graph?

Is there is any relation between bipartite graph, complete bipartite and planar graph?

Hira Thakur

502 views

Hira Thakur asked Nov 21, 2015

48 votes

3 answers

806

GATE CSE 1991 | Question: 16-b
Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.

Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.

Arjun

4.5k views

Arjun asked Nov 15, 2015

7 votes

1 answer

807

TIFR CSE 2012 | Part B | Question: 20
This question concerns the classes $P$ and $NP.$ If you are familiar with them, you may skip the definitions and go directly to the question. Let $L$ be a set. We say that $L$ is in $P$ if there is some algorithm which given input $x$ decides if ... $\text{MATCH} \notin P\text{ and } \overline{\text{MATCH}} \notin P$ none of the above

This question concerns the classes $P$ and $NP.$ If you are familiar with them, you may skip the definitions and go directly to the question.Let $L$ be a set. We say that...

Arjun

1.1k views

Arjun asked Nov 14, 2015

26 votes

4 answers

808

TIFR CSE 2013 | Part B | Question: 1
Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given different colours. Let $\chi (G)$ denote the chromatic number of $G$, i.e. the minimum ... $a\left(G\right)\leq \frac{n}{\chi \left(G\right)}$ None of the above

Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given di...

makhdoom ghaya

4.4k views

makhdoom ghaya asked Nov 5, 2015

17 votes

3 answers

809

TIFR CSE 2012 | Part B | Question: 2
In a graph, the degree of a vertex is the number of edges incident (connected) on it. Which of the following is true for every graph $G$? There are even number of vertices of even degree. There are odd number of vertices of even degree ... even number of vertices of odd degree. There are odd number of vertices of odd degree. All the vertices are of even degree.

In a graph, the degree of a vertex is the number of edges incident (connected) on it. Which of the following is true for every graph $G$?There are even number of vertices...

makhdoom ghaya

3.0k views

makhdoom ghaya asked Oct 30, 2015

18 votes

1 answer

810

TIFR CSE 2011 | Part B | Question: 33
Which of the following is NOT a sufficient and necessary condition for an undirected graph $G$ to be a tree? $G$ is connected and has $n -1$ edges. $G$ is acyclic and connected. $G$ is acyclic and has $n - 1$ edges. $G$ is acyclic, connected and has $n - 1$ edges. $G$ has $n - 1$ edges.

Which of the following is NOT a sufficient and necessary condition for an undirected graph $G$ to be a tree?$G$ is connected and has $n -1$ edges.$G$ is acyclic and conne...

makhdoom ghaya

2.1k views

makhdoom ghaya asked Oct 22, 2015

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