Recent questions and answers in Graph Theory

0 votes

1 answer

1

Seld doubt DM
Consider a tree T with n vertices and (n – 1) edges. We define a term called cyclic cardinality of a tree (T) as the number of cycles created when any two vertices of T are joined by an edge. Given a tree with 10 vertices, what is the cyclic cardinality of this tree?

answered 13 hours ago in Graph Theory by Shaik Masthan Veteran (50.1k points) | 9 views

0 votes

1 answer

2

Tripartite Graph
The number of vertices,edges and colors required for proper coloring in Tripartite graph K<3,2,5> will be : 10 , 31 , 3 10 , 30 , 3 10 , 30 , 2 None

answered 19 hours ago in Graph Theory by Priyadrasta Raut (117 points) | 11 views

+1 vote

1 answer

3

Vertex Connectivity
The Vertex Connectivity of Graph is : 1 2 3 None

answered 19 hours ago in Graph Theory by gate_dreams (297 points) | 10 views

0 votes

0 answers

4

Ace Academy Test series
If a 2 regular graph G has a perfect matching, then which of the following is NOT true? 1. G is a cycle graph 2. Chromatic number of G is 2 3. Every component of G is even cycle 4. G is a bipartite graph

asked 23 hours ago in Graph Theory by Chaitrasj Junior (799 points) | 21 views

0 votes

0 answers

5

How to do such questions.
If $G$ is a bipartite graph with 6 vertices and 9 edges, then the chromatic number of $\overline G$ =

asked 1 day ago in Graph Theory by `JEET Active (3.2k points) | 35 views

0 votes

2 answers

6

Made Easy CBT 19 Discrete Maths
How to solve it(clear explanation please)

answered 1 day ago in Graph Theory by Raja Rawal (457 points) | 62 views

0 votes

0 answers

7

MADE_EASY
The Number of Labelled possible graph given below ? what I did was → we doesn’t remove any of the edge out of 4 = $\binom{4}{0}$ [Because a Graph is sub-graph of itself] we can remove any of one edge out of 4 = $\binom{4}{1}$ we can remove any of the two edges out of 4 = $\binom{4}{2}$ similarly , $\binom{4}{3}$ , $\binom{4}{4 }$ then , add of the them

asked 1 day ago in Graph Theory by Magma Boss (12.7k points) | 26 views

0 votes

0 answers

8

How this question can be done.
if G is a bipartite graph with 9 vertices and maximum number of edges, then vertex connectivity of G =

asked 1 day ago in Graph Theory by `JEET Active (3.2k points) | 10 views

0 votes

1 answer

9

ME- CBT1
Can anyone explain how this is to be solved?

answered 2 days ago in Graph Theory by Manas Mishra Active (2.2k points) | 75 views

0 votes

0 answers

10

ACE Test series question on Chromatic number

asked 2 days ago in Graph Theory by Shankar Kakde (249 points) | 21 views

+23 votes

6 answers

11

TIFR2017-B-12
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles? $n$ $\frac{n(n-1)}{2}$ $n!$ $2^n$ $2^m, \: \text{ where } m=\frac{n(n-1)}{2}$

answered 3 days ago in Graph Theory by Varun Belliappa (121 points) | 1.4k views

+1 vote

1 answer

12

Graph Theory
Walk : Vertices may repeat. Edges may repeat (Closed or Open) Trail : Vertices may repeat. Edges cannot repeat (Open) Circuit : Vertices may repeat. Edges cannot repeat (Closed) Path : Vertices cannot repeat. Edges cannot repeat (Open) Cycle : Vertices cannot repeat. Edges cannot repeat (Closed) Can someone verify these terminologies? They are pretty confusing :/

answered 4 days ago in Graph Theory by gmrishikumar Junior (883 points) | 153 views

0 votes

0 answers

13

TRUE/FALSE
State TRUE/FALSE Squaring all edges will NOT change the maximum spanning tree Squaring all edges will NOT change the minimum spanning tree Squaring all edges will NOT change the second maximum spanning tree Squaring all edges will NOT change the second ... tree Cubing all edges will change the second maximum spanning tree Cubing all edges will change the second minimum spanning tree

asked 5 days ago in Graph Theory by Balaji Jegan Active (4.6k points) | 18 views

+54 votes

6 answers

14

GATE2012-38
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$

answered 6 days ago in Graph Theory by Hey (57 points) | 8.2k views

0 votes

0 answers

15

Graph_Self Doubt
Let G be a simple graph with 11 vertices . if degree of each vertex is atleast 3 and atmost 5 , then the number of edges in G should lie between I got 16 and 28

asked Jan 8 in Graph Theory by Magma Boss (12.7k points) | 52 views

0 votes

0 answers

16

rc test
Let G be a graph with 100 vertices numbered from 1 to 100. Two vertices i and j are adjacent if $\left | i-j \right |=8 $ or $\left | i-j \right |=12$ the number of connected components in G are a)8 b)4 c)12 d)25

asked Jan 8 in Graph Theory by Gate Fever Active (4.4k points) | 20 views

0 votes

0 answers

17

rc test series
Assume G is a connected planar graph that has 12 vertices and 17 regions.all interior regions are bounded by a cycle of length 3(ie 3 edge).find the number of edges bounding the interior region?

asked Jan 8 in Graph Theory by Gate Fever Active (4.4k points) | 38 views

0 votes

0 answers

18

rc test series
consider a simple graph G with k components.If each component has n1,n2,.....nk vertices,then the maximum number of edges in G is

asked Jan 8 in Graph Theory by Gate Fever Active (4.4k points) | 23 views

0 votes

0 answers

19

rc test series
A graph is said to be 2 colorable if each vertex can be colored either red or blue and no two vertices of the same color are connected by an edge.If some graph is not 2 colorable then we can reduce it to become 2 colorable by removing some edges.we are given ... graph 2 colorable (ex ;- k=0 if graph is already 2 colorable) the minimum value of k to reach the worst case is ______?

asked Jan 8 in Graph Theory by Gate Fever Active (4.4k points) | 16 views

0 votes

0 answers

20

GATEBOOK-2019 Grand Test Mathematics-6
Consider the adjacency matrix of undirected graph $G$ ... where chromatic partition is defined as the number of integer (positive) partitions possible for the chromatic number of $G$? $1$ $2$ $3$ $4$

asked Jan 7 in Graph Theory by GATEBOOK Boss (12.6k points) | 57 views

0 votes

0 answers

21

Made_easy_test_series
The number of totally ordered sets compatible to the given POSET are ________.

asked Jan 7 in Graph Theory by Shivam Kasat Active (1.6k points) | 55 views

+26 votes

8 answers

22

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$

answered Jan 7 in Graph Theory by Rajesh Panwar Junior (507 points) | 2.8k views

0 votes

0 answers

23

SELF DOUBT PLANARITY
IS THERE ANY SHORT TIME SAVING METHOD TO DETERMINE GRAPH IS PLANNER OR NOT

asked Jan 6 in Graph Theory by eyeamgj Loyal (6.6k points) | 23 views

0 votes

0 answers

24

self doubt
what is the chromatic number of null graph?

asked Jan 6 in Graph Theory by eyeamgj Loyal (6.6k points) | 25 views

0 votes

0 answers

25

Self Doubt: What is the strategy to color a graph with minimum colors?
I know the fact that if a graph has a complete subgraph, say Kn, at least n will be the chromatic number. But what is the strategy for coloring vertices of a graph so that we need minimum colors? Many times it has happened that the order in which I color leads to more number of colors.

asked Jan 6 in Graph Theory by Pratik Gawali Junior (827 points) | 8 views

0 votes

0 answers

26

simple graph formula
why in this planar graph this theorem ,”sum of degrees of faces or regions is twice the number of edges” is not true as it should hold for all planar graphs?? Note: numbers denote region or face

asked Jan 5 in Graph Theory by BHASHKAR (19 points) | 26 views

+8 votes

2 answers

27

ISI2015-PCB-C3
For a positive integer $n$, let $G = (V, E)$ be a graph, where $V = \text{{0,1}}^n$, i.e., $V$ is the set of vertices has one to one correspondence with the set of all $n$-bit binary strings and $E = \{(u,v) \mid u, v$ belongs to $V, u$ and $v$ differ in exactly one bit position$\}$. Determine size of $E$ Show that $G$ is connected

answered Jan 4 in Graph Theory by HeadShot Active (4.5k points) | 362 views

+47 votes

6 answers

28

GATE2014-1-51
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.

answered Jan 4 in Graph Theory by Prateek K Active (1.9k points) | 6.1k views

0 votes

0 answers

29

gate zeal mock
The Number of Relations, Which are both Reflexive and Symmetric but not Anti-Symmetric, on a set with 6 elements, are ____________? i got 32768 plz ceck

asked Jan 2 in Graph Theory by Prince Sindhiya Loyal (6.1k points) | 31 views

0 votes

0 answers

30

*** Test series
1.I is lattice, II is not lattice 2. I, II are not lattices 3.Both I, II are lattices 4. I is not lattice, II is lattice

asked Jan 2 in Graph Theory by piyushrawat01 (31 points) | 85 views

0 votes

0 answers

31

gate zeal mock
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex ... of degree 5, a vertex of degree 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex ____ ?

asked Jan 2 in Graph Theory by Prince Sindhiya Loyal (6.1k points) | 33 views

0 votes

0 answers

32

Basic Doubt
Statement : "Every Euler Graph is a simple graph" Please comment whether it is true always or need not to be. ( My concern is whether multi edge or self loop is allowed in euler graph or not i. e non-simple graph allowed or not )

asked Jan 2 in Graph Theory by HeadShot Active (4.5k points) | 33 views

0 votes

0 answers

33

madeeasy
How to calculate closed region and open region from given dara.

asked Jan 1 in Graph Theory by mehul vaidya Active (2.7k points) | 21 views

0 votes

0 answers

34

Eulerian Graph has to be connected?
A disconnected graph having even degree vertices can it be a euler graph? [closed]

asked Jan 1 in Graph Theory by sripo Active (1.3k points) | 50 views

+15 votes

3 answers

35

GATE2007-4
Let $G$ be the non-planar graph with the minimum possible number of edges. Then $G$ has 9 edges and 5 vertices 9 edges and 6 vertices 10 edges and 5 vertices 10 edges and 6 vertices

answered Dec 31, 2018 in Graph Theory by Badayayash (47 points) | 2.4k views

0 votes

0 answers

36

What to study & from where to study - Graph Theory for GATE 2019.
Are the following topics necessary/ apt to study for gate.(Bold items are explicitly mentioned in gate syllabus document) Connectivity Matching Coloring Cuts Covering Independent Sets Planar Graphs Isomorphism Walks, Trails, Paths, ... taking a lot of time. Can anyone please recommend a reliable and simple resource to go with.

asked Dec 29, 2018 in Graph Theory by Krishna Sai Vootla (23 points) | 51 views

0 votes

1 answer

37

ACE Test Series

answered Dec 28, 2018 in Graph Theory by Prince Sindhiya Loyal (6.1k points) | 44 views

0 votes

0 answers

38

edge and vertex connectivity
how solve getting different answer???

asked Dec 27, 2018 in Graph Theory by altamash (417 points) | 30 views

0 votes

0 answers

39

NTA NET Dec 2018 Q2

asked Dec 25, 2018 in Graph Theory by Sanjay Sharma Veteran (50.2k points) | 56 views

0 votes

0 answers

40

ME Test Series

asked Dec 23, 2018 in Graph Theory by Shadan Karim Junior (939 points) | 38 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