Test: Graphs Theory- 1

If the graph is planar, then it must follow below Euler's Formula for planar graphs

v - e + f = 2
v is number of vertices
e is number of edges
f is number of faces including bounded and unbounded

10 - 15 + f = 2
f = 7
There is always one unbounded face, so the number of bounded faces =  6

See Graph isomorphism

There can be total ⁶C₄ ways to pick 4 vertices from 6. The value of ⁶C₄ is 15. Note that the given graph is complete so any 4 vertices can form a cycle. There can be 6 different cycle with 4 vertices. For example, consider 4 vertices as a, b, c and d. The three distinct cycles are cycles should be like this (a, b, c, d,a) (a, b, d, c,a) (a, c, b, d,a) (a, c, d, b,a) (a, d, b, c,a) (a, d, c, b,a) and (a, b, c, d,a) and (a, d, c, b,a) (a, b, d, c,a) and (a, c, d, b,a) (a, c, b, d,a) and (a, d, b, c,a) are same cycles. So total number of distinct cycles is (15*3) = 45. **NOTE**: In original GATE question paper 45 was not an option. In place of 45, there was 90.  

A Graph is said to be planar if it can be drawn in a plane without any edges crossing each other. Following are planar embedding of the given two graph

The expression ξ(G) is basically sum of all degrees in a tree.   For example, in the following tree, the sum is 3 + 1 + 1 + 1.

Now the questions is, if sum of degrees in trees are same, then what is the relationship between number of vertices present in both trees? The answer is, ξ(G) and ξ(T) is same for two trees, then the trees have same number of vertices. It can be proved by induction. Let it be true for n vertices. If we add a vertex, then the new vertex (if it is not the first node) increases degree by 2, it doesn't matter where we add it. For example, try to add a new vertex say 'e' at different places in above example tee.

A generic algorithm or method to solve this question is 1: procedure isV alidDegreeSequence(L) 2: for n in list L do 3: if L doesn’t have n elements next to the current one then return false 4: decrement next n elements of the list by 1 5: arrange it back as a degree sequence, i.e. in descending order 6: if any element of the list becomes negative then return false 7: return true Rationale behind this method comes from the properties of simple graph. Enumerating the f alse returns, 1) if L doesn’t have enough elements after the current one or 2) if any element of the list becomes negative, then it means that there aren’t enough nodes to accommodate edges in a simple graph fashion, which will lead to violation of either of the two conditions of the simple graph (no self-loops and no multiple-edges between two nodes), if not others. 

: → According to this theorem, Let D be sequence the d1,d2,d2. . . dn with d1 ≥ d2 ≥ d2 ≥ . . . dn for n≥ 2 and di ≥ 0. → Then D0 be the sequence obtained by: → Discarding d1, and → Subtracting 1 from each of the next d1 entries of D. → That is Degree sequence D0 would be : d2-1, d2-1, d3-1 . . . , dd1+1 -1 . . . , dn → Then, D is graphical if and only if D0 is graphical. Now, we apply this theorem to given sequences: option I) 7,6,5,4,4,3,2,1 → 5,4,3,3,2,1,0 → 3,2,2,1,0,0 → 1,1,0,0,0 → 0,0,0,0 so its graphical. Option II) 6,6,6,6,3,3,2,2 → 5,5,5,2,2,1,2 ( arrange in ascending order) → 5,5,5,2,2,2,1 → 4,4,1,1,1,0 → 3,0,0,0,0 → 2,-1,-1,-1,0 but d (degree of a vertex) is non negative so its not a graphical. Option III) 7,6,6,4,4,3,2,2 → 5,5,3,3,2,1,1 → 4,2,2,1,1,0 → 1,1,0,0,0 → 0,0,0,0 so its graphical. Option IV) 8,7,7,6,4,2,1,1 , here degree of a vertex is 8 and total number of vertices are 8 , so it’s impossible, hence it’s not graphical. Hence only option I) and III) are graphic sequence and answer is option-D

The chromatic number of a graph is the smallest number of colours needed to colour the vertices of so that no two adjacent vertices share the same colour. These types of questions can be solved by substitution with different values of n. 1) n = 2

This simple graph can be coloured with 2 colours. 2) n = 3 

Here, in this graph let us suppose vertex A is coloured with C1 and vertices B, C can be coloured with colour C2 => chromatic number is 2 In the same way, you can check with other values, Chromatic number is equals to 2

A simple graph with no odd cycles is bipartite graph and a Bipartite graph can be colored using 2 colors (See this)

Since the graph is simple, there must not be any self loop and parallel edges. Since the graph is connected, the degree of any vertex cannot be 0. Therefore, degree of all vertices should be be from 1 to n-1. So the degree of at least two vertices must be same.

A planar graph is a graph which can drawn on a plan without any pair of edges crossing each other. A) FALSE: A disconnected graph can be planar as it can be drawn on a plane without crossing edges. B) FALSE: An Eulerian Graph may or may not be planar.An undirected graph is eulerian if all vertices have even degree. For example, the following graph is Eulerian, but not planar C) TRUE: D) FALSE:

Counter for option D is as follows. Take two copies of K4(complete graph on 4 vertices), G1 and G2. Let V(G1)={1,2,3,4} and V(G2)={5,6,7,8}. Construct a new graph G3 by using these two graphs G1 and G2 by merging at a vertex, say merge (4,5). The resultant graph is two edge connected, and of minimum degree 2 but there exist a cut vertex, the merged vertex.

Explanation: According to Kuratowski’s Theorem, a graph is planar if and only if it does not contain any subdivisions of the graphs K₅ or K_3,3.

That means K₅ and K_3,3 are minimum non-planar graphs. These graphs have 5 vertices with 10 edges in K₅ and 6 vertices with 9 edges in K_3,3 graph.
So, graph K₅ has minimum vertices and maximum edges than K_3,3.

Alternative method:
A plane graph having ‘n’ vertices, cannot have more than ‘2*n-4’ number of edges. Hence using the logic we can derive that for 6 vertices, 8 edges is required to make it a plane graph. So adding one edge to the graph will make it a non planar graph.

So, 6 vertices and 9 edges is the correct answer.

A graph has Eulerian Circuit if following conditions are true. ….a) All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges). ….b) All vertices have even degree. Let us analyze all options. A) Any k-regular graph where k is an even number. is not Eulerian as a k regular graph may not be connected (property b is true, but a may not) B) A complete graph on 90 vertices is not Eulerian because all vertices have degree as 89 (property b is false) C) The complement of a cycle on 25 vertices is Eulerian. In a cycle of 25 vertices, all vertices have degree as 2. In complement graph, all vertices would have degree as 22 and graph would be connected.

If we reverse directions of all arcs in a graph, the new graph has same set of strongly connected components as the original graph. Se 

Given: The vertex set of G is {(i, j): 1 <= i <= 12, 1 <= j <= 12}. There is an edge between (a, b) and (c, d) if |a − c| <= 1 and |b − d| <= 1.
There can be total 12*12 possible vertices. The vertices are (1, 1), (1, 2) ....(1, 12) (2, 1), (2, 2), ....
The number of edges in this graph? Number of edges is equal to number of pairs of vertices that satisfy above conditions.For example, vertex pair {(1, 1), (1, 2)} satisfy above condition.
For (1, 1), there can be an edge to (1, 2), (2, 1), (2, 2). Note that there can be self-loop as mentioned in the question. Same is count for (12, 12), (1, 12) and (12, 1)
For (1, 2), there can be an edge to (1, 1), (2, 1), (2, 2), (2, 3), (1, 3)
Same is count for (1, 3), (1, 4)....(1, 11), (12, 2), ....(12, 11) For (2, 2), there can be an edge to (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)
Same is count for remaining vertices. For all pairs (i, j) there can total 8 vertices connected to them if i and j are not in {1, 12} There are total 100 vertices without a 1 or 12. So total 800 edges. For vertices with 1, total edges = (Edges where 1 is first part) + (Edges where 1 is second part and not first part) =
(3 + 5*10 + 3) + (5*10) edges Same is count for vertices with 12
Total number of edges:
= 800 + [(3 + 5*10 + 3) + 5*10] + [(3 + 5*10 + 3) + 5*10]
= 800 + 106 + 106
= 1012
Since graph is undirected, two edges from v1 to v2 and v2 to v1 should be counted as one.
So total number of undirected edges = 1012/2 = 506.

The required graph is not possible with the given degree set of (3, 3, 3, 1, 0, 0). Using this 6-tuple the graph formed will be a Disjoint undirected graph, where the two vertices of the graph should not be connected to any other vertex ( i.e. degree will be 0 for both the vertices ) of the graph. And for the remaining 4 vertices the graph need to satisfy the degrees of (3, 3, 3, 1).

Let's see this with the help of a logical structure of the graph :

Let's say vertices labelled as <ABCDEF> should have their degree as <3, 3, 3, 1, 0, 0> respectively.

Now E and F should not be connected to any vertex in the graph. And A, B, C and D should have their degree as <3, 3, 3, 1> respectively. Now to fulfill the requirement of A, B and C, the node D will never be able to get its degree as 1. It's degree will also become as 3. This is shown in the above diagram.

Hence tuple <3, 3, 3, 1, 0, 0> is not graphic.

Number of edges would be maximum when there are 6 edges on each side and every vertex is connected to all 6 vertices of the other side.

Below is a cyclic graph with 5 vertices and its complement graph.

The complement graph is also isomorphic (same number of vertices connected in same way) to given graph.