Recent questions and answers in Graph Theory

0 votes

1 answer

1

Graphs

answered 22 hours ago in Graph Theory by Shaik Masthan Loyal (7.3k points) | 34 views

0 votes

0 answers

2

SELF DOUBT
https://gateoverflow.in/510/gate1991-01-xv IN THIS QUESTION I AM SOLVING LIKE THIS WE HAVE K COMPONENTS 1,2,3,.................K EACH OF WHICH HAVE N1,N2,N3,.................NK VERTICES SO TOTAL NUMBER OF EDGES ARE N1(N1-1)/2 +N2(N2-1)/2...................NK(NK-1)/2 SO AT SOMEWHERE IN STEPS I REACHED TO 1/2((-N)+N12+N22.......NK2)) NOT GETTING FURTHER FROM HERE ..................

asked 2 days ago in Graph Theory by eyeamgj Active (2.8k points) | 15 views

0 votes

1 answer

3

Graphs
I think ans is option C , But will anybody explain the notation used in option D ?

answered 3 days ago in Graph Theory by abhishekmehta4u Boss (19.9k points) | 27 views

0 votes

0 answers

4

me test
A simple graph with n vertices is constructed by randomly and independently placing an edge between every two vertices with probability p. What is the expected no. of nodes with degree 2?

asked 4 days ago in Graph Theory by ronin_codex (7 points) | 14 views

+1 vote

0 answers

5

Graph Theory

asked 6 days ago in Graph Theory by Bhagyashree Mukherje (165 points) | 40 views

0 votes

0 answers

6

graph theory
10.A graph G has any two vertices connected by exactly one path. Find the Number of ways we can properly colour G it we are provided with 10 colours.

asked Jul 14 in Graph Theory by poojasharma123 (75 points) | 66 views

+11 votes

2 answers

7

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

answered Jul 12 in Graph Theory by Prince Sindhiya Active (1.1k points) | 938 views

0 votes

0 answers

8

UGC NET JULY 2018 Q81

asked Jul 10 in Graph Theory by Sanjay Sharma Boss (48.6k points) | 36 views

+1 vote

1 answer

9

SELF DOUBT PREFIX
WE CAN USE STACK TO EVALUATE PREFIX EXPRESSION .THIS STATEMENT IS TRUE OR FALSE IF THEN HOW?? EXPRESSION IS + - * 2 3 5 / ^ 2 3 4

answered Jul 8 in Graph Theory by abhishekmehta4u Boss (19.9k points) | 35 views

0 votes

0 answers

10

kenneth rosen
Given n+1 symbols x1,x2,...,xn,xn+1 appearing 1, f1,f2,...,fn times in a symbol string, respectively, where fj is the jth Fibonacci number, what is the maximum number of bits used to encode a symbol when all possible tie-breaking selections are considered at each stage of the Huffman ... of symbols should be n+1 i.e 7 (in this case ansewr is 8)or n i.e 6( in this case answer is 6)??? [closed]

asked Jul 8 in Graph Theory by eyeamgj Active (2.8k points) | 46 views

0 votes

1 answer

11

SELF DOUBT DM ROSEN
Find the least number of comparisons needed to sort ﬁve element. I AM GETTING 7 AS (LOG 5!) =7........

answered Jul 8 in Graph Theory by Deepakk Poonia (Dee) Boss (17k points) | 26 views

0 votes

1 answer

12

rosen

answered Jul 7 in Graph Theory by Shaik Masthan Loyal (7.3k points) | 47 views

0 votes

2 answers

13

self doubt
Is it necessary that euler graph should always be simple graph?

answered Jul 6 in Graph Theory by kavya kamish upadhya (133 points) | 44 views

0 votes

0 answers

14

Gate 2018 Qn. 43
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 and if and only if the label of can be obtained by swapping two adjacent numbers in the label of . Let denote the degree of a vertex in G, and denote the number of connected components in G. Then, y + 10z = _____.

asked Jul 6 in Graph Theory by Optimus Prime (425 points) | 28 views

+1 vote

1 answer

15

self doubt
in a rooted tree if we are asked to find the level of root then it should be 0 or 1 or question depending ??

answered Jul 5 in Graph Theory by abhishekmehta4u Boss (19.9k points) | 26 views

+1 vote

2 answers

16

Graph Theory
Can someone solve this? Also please attempt this question on Algorithms time complexity if interested :) https://gateoverflow.in/210836/algorithms-time-complexity

answered Jul 1 in Graph Theory by nandini gupta Active (1.6k points) | 88 views

0 votes

0 answers

17

How to find even or odd cylce in a graph

asked Jun 30 in Graph Theory by ejaz (205 points) | 22 views

+1 vote

2 answers

18

Graph Theory Question
Consider a social network with n persons. Two persons A and B are said to be connected if either they are friends or they are related through a sequence of friends: that is, there exists a set of persons F1, . . . , Fm such that A and F1 ... . It is known that there are k persons such that no pair among them is connected. What is the maximum number of friendships possible?

answered Jun 22 in Graph Theory by himanshu19 Junior (715 points) | 281 views

+1 vote

2 answers

19

Graph Theory- vertex degree
Consider an undirected graph with n vertices, vertex 1 has degree 1, while each vertex 2,3......, n – 1 has degree 4. The degree of vertex n is unknown. Which of the following statement must be TRUE? a. Vertex n has degree 1. b. Graph is connected. c. There is a path from vertex 1 to vertex n. d. Spanning tree will include the edge connecting vertex 1 and n.

answered Jun 22 in Graph Theory by himanshu19 Junior (715 points) | 142 views

+3 votes

1 answer

20

Graph Coloring
A vertex colouring with four colours of a graph G = (V, E) is a mapping V → {R, G, B, Y }. So that any two adjacent vertices does not same colour. Consider the below graphs: The number of vertex colouring possible with 4 colours are _________. ... Red and D with also blue which is other than Green, now this case is clearly violating graph coloring property. How, to solve this one?

answered Jun 21 in Graph Theory by Prashank (79 points) | 112 views

0 votes

1 answer

21

spanning tree
How we get maximum no. of spanning tree for give $n$ node is $n^{(n-2)}$

answered Jun 18 in Graph Theory by Anil Ji Active (3.1k points) | 22 views

0 votes

0 answers

22

Kenneth rosen
How many non-isomorphic directed graphs are there with $n$ vertices when $n$ is $2$ $3$ $4$

asked Jun 18 in Graph Theory by swati96 (37 points) | 27 views

0 votes

0 answers

23

Kenneth rosen
How many non-isomorphic graphs are there with six vertices and four edges?

asked Jun 18 in Graph Theory by swati96 (37 points) | 8 views

0 votes

0 answers

24

Graphs, kenneth rosen
How many non-isomorphic simple graphs are there with five vertices and three edges?

asked Jun 18 in Graph Theory by swati96 (37 points) | 14 views

0 votes

0 answers

25

Graphs, kenneth rosen
How many non-isomorphic simple graphs are there with five vertices and three edges? [closed]

asked Jun 18 in Graph Theory by swati96 (37 points) | 10 views

+1 vote

2 answers

26

planar graphs
Is there any subgraph homoemorphic to K5 present in G1 for the following question? Which one of the following graphs is NOT planar? (A) G1 (B) G2 (C) G3 (D) G4 In this question planar drawings( no 2 edges intersect) for G2, G3 and G4 exists, thats why ... 't find any subgraph homoemorphic to K5 in G1 as a graph is non planar iff it contains a subgraph homoemorphic to K5 or K3,3...

answered Jun 17 in Graph Theory by Prashank (79 points) | 322 views

0 votes

1 answer

27

Perfect Matching
Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (EXACTLY one appearance). So for n vertices perfect matching will have n/2 edges and there won't be any perfect matching if n is odd. ... 't know whether i got it properly or not. Can please anybody explain the Perfect matching in a complete graph with simpler examples ?

answered Jun 10 in Graph Theory by srestha Veteran (88.9k points) | 30 views

0 votes

1 answer

28

True/False
Which of the following statements related to graphs are True? Consider a graph with Positive distinct edges 1.If we add a Positive Integer to all edges, then there are chances to get more than one shortest paths between 2 vertices 2.If we add a Positive Integer ... 4.If we add a Negative Integer to all edges, then there are chances to get more than one longest paths between 2 vertices

answered Jun 9 in Graph Theory by Deepakk Poonia (Dee) Boss (17k points) | 51 views

0 votes

0 answers

29

[4-14]Connectivity- Narsingh Deo
Show that a simple graph is nonseparable iff for any two given arbitrary edges a circuit can always be found that will include these two edges.

asked Jun 8 in Graph Theory by Ayush Upadhyaya Boss (10.4k points) | 26 views

0 votes

0 answers

30

[4-13]Connectivity-Narsingh Deo
Show that a graph G is non-separable iff every vertex pair can be placed in some circuit in G.

asked Jun 8 in Graph Theory by Ayush Upadhyaya Boss (10.4k points) | 14 views

0 votes

2 answers

31

Connectivity(4-20) Narsingh Deo
Is every regular graph of degree d(d$\geq$3) non-separable?If not, give a simple regular graph of degree 3 that is separable.

answered Jun 8 in Graph Theory by Lakshay Kakkar Junior (961 points) | 67 views

0 votes

2 answers

32

Self-Doubt regarding Graph Coloring
This has reference to the below question https://gateoverflow.in/204092/gate2018-18?show=204092#q204092 My doubt is Suppose, I try to colour the vertices of this graph as follows First I colour vertex a and f with colour 1. Then I colour vertex e ... what points in mind do I need to remember so that I can colour any given graph with the minimum number of colours. [closed]

answered Jun 8 in Graph Theory by Shaik Masthan Loyal (7.3k points) | 73 views

0 votes

2 answers

33

Number of Subgraphs of Kn?
I was searching for this question and found below link How many subgraphs does $K_5$ have? Here, in general, it is given to be $\displaystyle\sum_{r=0}^{n}\binom{n}{r}2^{\frac{r(r-1)}{2}}$ My doubt is that the case for $r=0$ is taken if we select none of the vertices of $K_n$? Why the case for $ r=0$ considered?

answered Jun 7 in Graph Theory by Deepakk Poonia (Dee) Boss (17k points) | 40 views

+15 votes

7 answers

34

TIFR2015-B-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 matrix of an ... below has the above adjacency matrix? Only $(i)$ Only $(ii)$ Only $(iii)$ Only $(iv)$ $(i)$ and $(ii)$

answered Jun 7 in Graph Theory by Ayush Upadhyaya Boss (10.4k points) | 623 views

+30 votes

5 answers

35

GATE2007-23
Which of the following graphs has an Eulerian circuit? Any $k$-regular graph where $k$ is an even number. A complete graph on $90$ vertices. The complement of a cycle on $25$ vertices. None of the above

answered Jun 6 in Graph Theory by Ayush Upadhyaya Boss (10.4k points) | 3.4k views

0 votes

0 answers

36

Number of distinct cycles of length 4 in a complete graph of 6 labelled vertices. [closed]

asked Jun 6 in Graph Theory by Ayush Upadhyaya Boss (10.4k points) | 57 views

0 votes

0 answers

37

Connectivity(4-10)-Narsingh Deo
Prove that in a connected graph G a vertex v is a cut-vertex if and only if there exist two(or more) edges x and y incident on v such that no circuit in G includes both x and y. [closed]

asked Jun 2 in Graph Theory by Ayush Upadhyaya Boss (10.4k points) | 38 views

+1 vote

2 answers

38

Whether the given pair of graphs is isomorphic?Pls provide a rigorous argument.

answered Jun 1 in Graph Theory by Prashank (79 points) | 423 views

0 votes

0 answers

39

Proper edge coloring
What is the minimal number K such that there exists a proper edge coloring of the complete graph on 8 vertices with K colors? A) 28 B) 8 C) 7 D) 15

asked Jun 1 in Graph Theory by Lakshman Patel RJIT Loyal (7.9k points) | 50 views

0 votes

0 answers

40

Keneth
Are there any graph having chromatic number 1 ??????

asked Jun 1 in Graph Theory by vijju532 (287 points) | 98 views

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

Recent Posts

Recent Blog Comments