# Recent questions and answers in Graph Theory

A tree has 14 vertices of degree 1 and degree of each of remaining vertices is 4 or 5. If the tree has ‘n’ vertices then number of vertices with degree 5 is:- (40-2n) (3n-54) (54-2n) (3n-40)
Hi There is 2 book for graph theory so which book is followed because is rosen is short for graph theory and deo is very detailed so for gate which book is followed ? in rosen so there is complete detail for graph theory so if i read rosen so can i make gate related questions or not ? thank you
Find the number of paths of length n between any two nonadjacent vertices in K3,3 for the following values of n: a)2 b)3. c)4. d)5 ( i am able to understand the number of paths of length n between any two adjacent vertices in K3,3… but i am not able to get intuition for non adjacent in the adjacency matrix)
1 vote
How many non-isomorphic graphs are possible with 6 edges 6 vertices each having a degree of 2? 2 4 5 6
Please explain the basic difference between Independent set and Dominating Set?
1 vote
In an undirected connected planar graph $G$, there are eight vertices and five faces. The number of edges in $G$ is _________.
Let $G=(V, E)$ be an undirected unweighted connected graph. The diameter of $G$ is defined as: $\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between$u$and$v$}\}$ Let $M$ be the adjacency matrix of $G$. Define graph $G_2$ on the same set of ... $\text{diam}(G_2) = \text{diam}(G)$ $\text{diam}(G)< \text{diam}(G_2)\leq 2\; \text{diam}(G)$
https://gateoverflow.in/83854/gate1990-1-viii The above is the link of the question. In the solution it was assumed that the graph is complete. But in the question nothing is mentioned. Also a complete graph doesn't contain self loops. So what I'm thinking is, if we consider the ... m is the number of the edges in the graph, then m = n^2 - m should be the condition. Please let me know about this!
1 vote
consider a cycle graph of 4 vertices and needs to perform the vertex coloring using 4 colors. The maximum number of vertex colorings possible is (Answer given as 68)
What will be the number of components?
Consider G(V, E) be a complete undirected graph with 6 edges having a distinct weight from 1, 3, 9, 27, 81, and 243. Which of the following will NOT be the weight of them minimum spanning tree of G? (*This question may have multiple correct answers) A)121 B)13 C)40 D)31
A graph which not having even length cycle then 3 color are sufficient to color vertices of graph such that no two adjacent vertex having same color?
Which of the following options are not the chromatic polynomial of the following graph: a) b) c) d) can someone explains?
Let G be a Graph with V(G)={i|1<=i<=4n} where V(G) is the set of vertices of G. such that two numbers x and y are adjacent iff (x+y) is a multiple of 4. Find the number of the connected component in graph G 2 4 N None of these From the above k components, assume that each component Ck has mk vertices, then what is the maximum value of mk in the graph n 2n 3n None of these
1 vote
Siruseri Traffic Lights Adapted from Traffic Lights, International Olympiad in Informatics, 1999 In Siruseri, there are junctions connected by roads. There is at most one road between any pair of junctions. There is no road connecting a junction to itself. The travel time for a road is the same in both directions. ... . 1 to 3 to 2 to 4 takes time 8 + 0 (no wait) + 6 + 1 (wait till 15) + 10 = 25.
1 vote
Let G be a graph with n vertices and if every vertex has a degree of at least $\frac{n−1}{2}$ then G is connected. Source : https://gateoverflow.in/1221/gate2007-23 Let G be a graph with n vertices and if every vertex has a degree of at least $\frac{n}{2}$ then G is connected. source : https://nptel.ac.in/courses/106/106/106106183/ My doubt : Which one is right?
$K_5$ is non-planar. I am showing you my proof. Please tell me whether this is the right way or not to prove that $K_5$ is non-planar. $\sum$ (deg)$=4+4+4+4+4=20$ $e=10$ and $n=5$ Assume $K_5$ is planar. $v-e+r=2$ $5-10+r=2$ $r=7$ Now ... $K_5$ is non-planar. If this is the right way, why this method didn't work in this graph. Source: https://gateoverflow.in/87129/gate1990-3-vi
The chromatic number of a star graph with n vertices (n≥ 2) is ________.
The maximum number of edges in a bipartite graph on 12 vertices is _________. Please tell any generalized solution for this problem, if exists.
Number of cycles of length 4 that are possible in the complete bipartite graph K(4,6) is
Construct a graph G with the following properties: edge connectivity of G =4, Vertex connectivity of G=3, and degree of every vertex of G >=5.
S1: A tree with n vertices which has no vertices of degree 2 must have at least leaves S2: The number of trees on 5 labelled vertices is 125. Which of the following statements is true? (A). Only S1 (B). Only S2 (C). Only S1 and S2 (D). None of the above
theorem: HALL’S MARRIAGE THEOREM-The bipartite graph G=(V,E) with bipartite (v1,v2) has a complete matching from v1 to v2 if and only if |N(A)$\geq$|A| for all subsets of A of V1. explain with example
THE FOUR COLOR THEOREM: The chromatic number of a planar graph is no greater than four. Question #40 (10.8) : Show that every planar graph G can be colored using six or fewer colors. Question #41 (10.8) : Show that every planar graph G can be colored using five ... questions if it is already stated in the four color theorem that we don't require more than 4 colors in order to color a planar graph.
I was working from the famous book of Deo. Then i found this problem very hard and interesting. Any ideas to give me? - Let us define a new term called edge isomorphism as follows: Two graphs G1 and G2 are edge isomorphic if there is a one-to- ... are also incident in G2. Discuss the properties of edge isomorphism. Construct an example to prove that edge-isomorphic graphs may not be isomorphic.
What is the degree of region r4? How you find it?
How many number of cut vertex in tree if n is the number total vertex in tree?
How to count number of labeled simple graphs? Please explain!
Suppose that $d_{1}, d_{2}, ..., d_{n}$ is a graphic sequence. Show that there is a simple graph with vertices $v_{1}, v_{2}, …, v_{n}$ such that deg($v_{i}$) = $d_{i}$ for i = 1,2, …, n and $v_{1}$ is adjacent to $v_{2}, …, v_{d1 + 1}$.
what is Degree of Self loop in undirected graph? Is it 2 or 1? please give a proper source
Find number of perfect matching in Kn where n is even? Please explain too?
How many m len cycles in complete graph of n vertices? Please explain.
What are number of independent sets in Complete graph?