Graph Theory | Engineering Mathematics

In graph theory, A graph is called regular graph if degree of each vertex is equal.
A regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree

Let us say,
degree = d
vertices = n
Total degrees of all the vertices is n*d
Each edge will be increasing the total degree by 2,
So Total edges = nd/2

Alternative :
By handshaking Lemma:
In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that
sum of degrees = 2 * number of edges
n × d = 2 × e
E=nd/2

A directed graph is strongly connected if there is a path between all pairs of vertices

The given graph has (a, b, c) as a strongly connected component.

Theorem : In any graph G with e edges, the sum of the degrees of all the vertices = 2* e

Alternative

By handshaking Lemma:
In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that
sum of degrees = 2 * number of edges
n × d = 2 × e
.

Theorem : In any graph G with e edges, the sum of the degrees of all the vertices = 2* e.

Alternative :

By handshaking Lemma:
In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that
sum of degrees = 2 * number of edges
n × d = 2 × e

Theorem : In any graph G with e edges, the sum of the degrees of all the vertices = 2* e.

Alternative :

By handshaking Lemma:
In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that
sum of degrees = 2 * number of edges
n × d = 2 × e

Euler Graph :
A given connected graph G is a Euler Graph if and only if all vertices of G are of even degree.
(OR)
An Euler Graph is a connected graph that contains an Euler Circuit.
So option(B) is correct answer

Above graph is a connected graph and all its vertices are of even degree. So, it is an Euler graph.
Alternatively, the above graph contains an Euler circuit BACEDCB, Therefore, it is an Euler graph.

Maximum number of edges in a undirected graph with n nodes ?
In a graph with N vertices we can draw an edge from a vertex to (N−1) vertex like that we will do it for N vertices so total number of edges is N(N−1) now each edge is counted twice so the required maximum number of edges is N(N−1)/2.

Maximum number of edges in a directed graph with n nodes ?
If you have N nodes, there are N - 1 directed edges than can lead from it (going to every other node). Therefore, the maximum number of edges is N * (N - 1).

Alternative :
The maximum number of edges in an n node undirected graph G (n, e) without self-loops is present in a complete graph (Kn):

A complete graph is a graph with N vertices and an edge between every two vertices.

• There are no loops.
• Every 2 vertices share exactly one edge.

We use the symbol K_N for a complete graph with N vertices.

Example : 

In graph theory, A graph is called regular graph if degree of each vertex is equal.
A regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree

Number of edges in a regular graph of degree d and n vertices is ?
By handshaking Lemma:
In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that
sum of degrees = 2 * number of edges
n × d = 2 × e
E=nd/2

Complete graph
A complete graph is a graph with N vertices and an edge between every two vertices.

• There are no loops.
• Every 2 vertices share exactly one edge.

We use the symbol K_N for a complete graph with N vertices.

Example : 


Multigraph
a multigraph is a graph which is permitted to have multiple edges (also called parallel edges), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge.

Theorem : If in a graph G there is one and only one path between every pair of vertices than graph G is a tree.
Proof: There is the existence of a path between every pair of vertices so we assume that graph G is connected. A circuit in a graph implies that there is at least one pair of vertices a and b, such that there are two distinct paths between a and b. Since G has one and only one path between every pair of vertices. G cannot have any circuit. Hence graph G is a tree.

If a vertex is removed from the graph G, with n nodes and k components
Minimum :
Number of components decreased by one = k−1 (The removed vertex itself is a isolated vertex which was a component)
Maximum:
Number of components =n−1 ( consider a vertex connected to all other vertices in a component as in a star and all other vertices outside this component being isolated. Now, removing the considered vertex makes all other n−1 vertices isolated making n−1 components)

A forest is a graph with no cycles; a tree is a connected graph with no nontrivial closed trails.
Thus, a forest is a disjoint union of trees.
Each connected component is a tree

Complete graph
A complete graph is a graph with N vertices and an edge between every two vertices.

• There are no loops.
• Every 2 vertices share exactly one edge.

We use the symbol K_N for a complete graph with N vertices.

Example : 

To guarantee correction of upto t errors, the minimum Hamming distance dmin in a block code must be dmin = 2t + 1

• The Hamming distance between two words is the number of differences between corresponding bits.
• To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be dmin = s+1.
• To guarantee correction of up to t errors in all cases, the minimum Hamming distance in a block code must be dmin = 2t + 1.
•  k – number of data bits, r – number of redundant bits, n – Number of code bits
•  n = k + r
• 2^r ≥ k + r + 1 where, r = redundant bit, k = data bit
•  Example : k = 4; then r = 3

P : Number of odd degree vertices is even - True


Q: Sum of degrees of all vertices is even - True
By handshaking Lemma:
In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

• The sum of degree of all the vertices is always even.
• The sum of degree of all the vertices with odd degree is always even.
• The number of vertices with odd degree are always even.

• An edge in an undirected connected graph is a bridge if removing it disconnects the graph.
• For a disconnected undirected graph : A bridge is an edge removing which increases number of disconnected components
• If we remove { d-e } edge then there is no way to reach out to vertex e and the graph is disconnected.
• So, In the above given graph only edge {d-e} is a bridge since its removal produces 2 components.

The above graph has no Euler circuit because Graph is not connected.

Concept :

A Hamiltonian circuit is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex. A Hamiltonian path also visits every vertex once with no repeats, but does not have to start and end at the same vertex.
Option(A) : It is not Hamiltonian circuit because A,F and E are repeated several times.
Option(B) : It is not Hamiltonian circuit because start and end vertex are different it means, not closed walk.
Option(C) : It is Hamiltonian circuit because it is closed walk it means, start and end vertex are same and all vertex are traversed once with no repeats.
Option(D) : It is not Hamiltonian circuit because it is not closed walk.

• In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
• In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph.
• A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Graph that can be 2-colored are bipartite graph. To check if a given graph is bipartite, we run BFS starting from any node then we check

if there is any edge between two nodes in the same BFS levels the graph is bipartite iff there is no such edge.

A k- coloring of a graph G is mapping f: V(G) -> {set of k elements called colors}, such that adjacent vertices are mapped onto different elements.

A graph is called k – colourable, if it has a k-coloring. A k-coloring of a graph G(V, E) is a partitioning
V = V1 U V2 U V3 ………… U Vk into at most k independent sets of G.

A bipartite graph is a special kind of graph with the following properties-

• A cycle of length n>=3 is – chromatic if n is even and 3- chromatic if n is odd
• A graph is bi- colourable (2- chromatic) if and only if it has no odd cycles.
• A non - empty graph G is bi colourable if and only if G is bipartite.

In an Hamiltonian Graph (G) with no loops and parallel edges:

According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.
So Statement(i) is false

According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.
So Statement(ii) is True

The maximum number of edges for a graph to be non-hamiltonian is ⁽ⁿ⁻¹⁾C₂+1.
Refer this link : https://math.stackexchange.com/questions/91975/maximum-number-of-edges-in-a-non-hamiltonian-graph

Statement(iii) : E(G) ≥ 1/3(n−1)(n−2) + 2

Consider n=4,

⁴⁻¹C₂ + 1=3+1=4. therefore, if the number of edges is ≤4, then the graph can be non-hamiltonian

E(G) ≥ 1/3(4−1)(4−2)+2 ≥ 4, this says for E(G)≥4 the graph should be hamiltonian, but for E(G)=4 the graph can be non-hamiltonian.

  |E(G)| ≥ 1/2(n – 1) (n – 2) + 2
Any graph with n vertices and at least 1/2 (n−1) (n−2)+2 edges must be hamiltonian.
Refer : https://www.quora.com
Therefore, Statement(iii) is false.

So, option (D) is correct.

For any circuit or network,
M = B - n + 1
Where,
M = Number of mesh (independent loop)
B = Number of branches
n = Number of nodes

Concept :

• For a circuit with n nodes, there are n − 1 independent node equations that constrain the currents. If the circuit has b branches, that implies that there are exactly b−(n−1) = b−n+ 1 independent loops currents.
• For planar circuits (circuits that can be drawn on a plane without any elements crossing one another), there is an obvious choice for the loops; namely, the b − n + 1 small loops that enclose no circuit elements.
• For nonplanar loops, the choice is not so obvious, but the number of independent loops will be b − n + 1

• A tree is a connected subgraph of a network which consists of all the nodes of the original graph but no closed paths.
• The graph of a network may have a number of trees.
• The number of nodes in a graph is equal to the number nodes in the tree. The number of branches in a tree is less than the number of branches in a graph.
• A graph is a tree if there is a unique path between any pair of nodes.'
• In general, if a tree contains n nodes, then it has (n-1) branches. In forming a tree for a given graph, certain branches are removed or opened.
• The branches thus opened are called links or link branches Thus the link branches and the tree branches combine to form the graph of the entire network.
• A circuit in such a tree is impossible.

• The minimum number k for which there is a k-colouring of the graph is called the chromatic number (chromatic index) of G and is denoted by χ(G). If χ(G) = k, the graph G is said to be k-chromatic.
• A complete graph with n vertices is n-chromatic, because all its vertices are adjacent. So, χ(K_n) = n and χ( K_n') = 1. Therefore we see that a graph containing a complete graph of r vertices is at least r-chromatic. For example, every graph containing a triangle is at least 3-chromatic.

Chromatic Number for cycle graph
1) Chromatic number is 2 If number of vertices in cycle graph is even
2)Chromatic number is 3 If number of vertices in cycle graph is odd
Option (D) : n-2⌈(n/2)⌉+2 is a representation for this. So Option(D) is correct Answer
Substitute n = 3 and n = 4 in given equation n-2⌈(n/2)⌉+2 . Then we will get the desired answer.

Example :

For any planar graph,

v - e + f = 2

Where,
v = Number of vertices
e = Number of edges
f = Number of faces including bounded and unbounded

f =15−10+2=7
Number of bounded faces =number of faces -1
=7−1=6
Therefore, option(D) is correct answer

By handshaking Lemma:
In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that
sum of degrees = 2 * number of edges
n × d = 2 × e

• A circuit is a walk that starts and ends at a same vertex, and contains no repeated edges.
• An Eulerian circuit in a graph G is a circuit that includes all vertices and edges of G. A graph which has an Eulerian circuit is an Eulerian graph.
• A Hamiltonian circuit in a graph G is a circuit that includes every vertex (except first/last vertex) of G exactly once.
• An Eulerian path in a graph G is a walk from one vertex to another, that passes through all vertices of G and traverses exactly once every edge of G. An Eulerian path is therefore not a circuit.
• A Hamiltonian path in a graph G is a walk that includes every vertex of G exactly once. A Hamiltonian path is therefore not a circuit.

• An edge in an undirected connected graph is a bridge if removing it disconnects the graph.
• For a disconnected undirected graph : A bridge is an edge removing which increases number of disconnected components
• If we remove { a-b } edge then there is no way to reach out to vertex b and then the graph is disconnected.
• If we remove { e-f } edge then there is no way to reach out to vertex f and then graph is disconnected.
• So, In the above given graph only edge { a-b } and { e-f }  are bridges since its removal produces 3 components.

Eulerian Path is a path in graph that visits every edge exactly once. An Eulerian path is therefore not a circuit. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.
True : The existence of an Euler circuit implies that an Euler path exists.
False : The existence of an Euler path implies that an Euler circuit exists.

For any planar graph,

v - e + R = 2

Where,
v = Number of vertices
e = Number of edges
Number of regions/faces(R/f)=?

For any connected planner graph
V-E+R=2;
V+R=E+2;
R=E-V+2;
R=13−8+2=7
R=15−8=7
∴  Number of regions in given graph G is 7
Therefore, option(C) is correct answer

For any planar graph,

v - e + f = 2

Where,
v = Number of vertices
e = Number of edges
f = Number of faces
Given,
vertex v =13
Edges e =19
v - e + f = 2
v + f = e+2
f = e-v+2
f=19-13+2
f=21-13
f=8
Therefore, option(B) is correct answer

For any planar graph,

v - e + f = 2

Where,
v = Number of vertices
e = Number of edges
f = Number of faces

Given,
vertex v =4
Faces f=4
Edges e =?

v - e + f = 2
4-e+4=2
-e+8=2
8=2+e
e=8-2
e=6

Therefore, option(B) is correct answer

If every minimal cut has an even number of edges, then in particular the degree of each vertex is even. Since the graph is connected, that means it is Eulerian.

Theorem. A graph G is bipartite if and only if it has no odd cycles.
Proof. First, suppose that G is bipartite. Then since every subgraph of G is also bipartite, and since odd cycles are not bipartite, G cannot contain an odd cycle. That’s the easy direction. Now suppose that G is a non-trivial graph that has no odd cycles. We must show that G is bipartite. So we must determine a partition of the vertices of G into independent sets. It is enough to prove our result for connected graphs since if G is bipartite, so is every component of G (and vice versa).
Refer page number 2: https://people.math.sc.edu/sumner/math575spring2009/handouts/Bipartite%20graphs.pdf 

Bipartite Graph: A graph which is 2-colorable is called bipartite.
Refer page number 5 : https://ocw.mit.edu/high-school/mathematics/combinatorics-the-fine-art-of-counting/lecture-notes/MITHFH_lecturenotes_9.pdf

Bipartite graphs: By definition, every bipartite graph with at least one edge has chromatic number 2.(otherwise 1 if graph is null graph )
Refer page number 1 : https://web.math.ucsb.edu/~padraic/mathcamp_2011/introGT/MC2011_intro_to_GT_wk1_day4.pdf

Chromatic Number=2 So, option(C)  is the correct answer.

P : Number of odd degree vertices is even - True


Q: Sum of degrees of all vertices is even - True
By handshaking Lemma:
In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

• The sum of degree of all the vertices is always even.
• The sum of degree of all the vertices with odd degree is always even.
• The number of vertices with odd degree are always even.

Given graphs are isomorphic if it satisfies the below rules

1. Equal number of vertices.
2. Equal number of edges.
3. Same degree sequence
4. Same number of circuit of particular length

Graph G and H are having same number of vertices and edges. Total Both the graphs have 6 vertices, 9 edges So, it satisfied first and second rule.

The degree sequence is also same.
→ M1 degree 2, M2 degree 3, M3 degree 3, M4 degree 2, M5 degree 3, M6 degree 3.
→ V1 degree 2,   V2 degree 3, V3 degree 3,  V4 degree 2,  V5 degree 3,  V6 degree 3.

But second graph has a circuit of length 3 and the minimum length of any circuit in the first graph is 4. Therefore the given graphs are not isomorphic.

In graph theory, A graph is called regular graph if degree of each vertex is equal.
A regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree

Let us say,
degree = d
vertices = n
Total degrees of all the vertices is n*d
Each edge will be increasing the total degree by 2,
So Total edges = nd/2

Alternative :
By handshaking Lemma:
In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that
sum of degrees = 2 * number of edges
n × d = 2 × e
E=nd/2

• A minimal subgraph G’ of G such that V(G’)=V(G) and G’ is connected is called a spanning tree
• Spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible no. of edges. Therefore, a spanning tree does not contain any cycles and it cannot be disconnected.

In an Hamiltonian Graph (G) with no loops and parallel edges:
According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.
So Statement(i) is True

According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.
So Statement(iii) is True

The maximum number of edges for a graph to be non-hamiltonian is ⁽ⁿ⁻¹⁾C₂+1. Refer this link : https://math.stackexchange.com/questions/91975/maximum-number-of-edges-in-a-non-hamiltonian-graph

Statement(ii) :  |E(G)| ≥ 1/2(n – 1) (n – 2) + 2
Any graph with n vertices and at least 1/2 (n−1) (n−2)+2 edges must be hamiltonian.
Refer : https://www.quora.com
Therefore, Statement(ii) is True.

So, option (D) is correct.

Both G​₁​ and G_​2​ do not contain Euler circuit.
- G​₁ have odd number of vertices. So, it is not Euler Circuit
- G​₂ have odd number of vertices. So, it is not Euler Circuit

So, option(C) is the correct answer

Concept :
Criterion for Euler Path
If a graph G has an Euler path, then it must have exactly two odd vertices.
(Or)
If the number of odd vertices in G is anything other than 2, then G cannot have an Euler path.

 Criterion for Euler Circuits
If a graph G has an Euler circuit, then all of its vertices must be even vertices.
(Or)
If the number of odd vertices in G is anything other than 0, then G cannot have an Euler circuit.

For any complete graph K_n with n nodes, different spanning trees possible is n^(n-2)
Therefore, Number of spanning trees in complete graph K₄ will be 4^{(4 - 2)}=4² = 16.

For any Bipartite graph K_m,n with m and n nodes, different spanning trees possible is m^(n-1).n^(m-1)
Therefore, Number of Spanning trees in K_2,2 will be 2^(2-1) * 2^(2-1). = 2 * 2 = 4.

Definition already mentioned in the question.
Clique :
A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph

Therefore, Total 5 cliques are possible in the given graph

Statement(A) : True
Theorem 1. Euler’s Theorem. For a connected multi-graph G, G is Eulerian if and only if every vertex has even degree.
Proof: If G is Eulerian then there is an Euler circuit, P, in G. Every time a vertex is listed, that accounts for two edges adjacent to that vertex, the one before it in the list and the one after it in the list. This circuit uses every edge exactly once. So every edge is accounted for and there are no repeats. Thus every degree must be even.
Suppose every degree is even. We will show that there is an Euler circuit by induction on the number of edges in the graph. The base case is for a graph G with two vertices with two edges between them. This graph is obviously Eulerian
Refer : https://courses.engr.illinois.edu/cs173/su2014/Lectures/Euler.pdf

Statement(B) : True
Theorem 2 : A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.
Proof:
(ONLY IF) Assume the graph has an Euler path but not a circuit. Notice that every time the path passes through a vertex, it contributes 2 to the degree of the vertex (1 when it enters, 1 when it leaves). Obviously the first and the last vertices will have odd degree and all the other vertices - even degree. (IF) Assume exactly two vertices, u and v, have odd degree. If we connect these two vertices, then every vertex will have even degree. By Theorem 1, there is an Euler circuit in such a graph. If we remove the added edge {u,v} from this circuit, we will get an Euler path for the original graph.

Statement(C) : True
Theorem 3 : A complete graph (K​n​ ) has a Hamilton Circuit whenever n ≥ 3.
Proof : Let v1, . . . , vn be any way of listing the vertices in order. Then v1 − v2 − · · · − vn − v1 is a Hamilton circuit since all edges are present.
In general, having lots of edges makes it easier to have a Hamilton circuit.

Statement(D) : False

A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set.

Bipartite graphs are equivalent to two-colorable graphs that is coloring of the vertices using two colors in such a way that vertices of the same color are never adjacent along an edge.

Option(A) - FALSE
It is not bipartite graph because V₅ , V₇ and V₃ are adjacent.

Option(B) - FALSE
It is not bipartite graph because V₅ , V₆ and V₂ are adjacent.

Option(C) - TRUE
It is bipartite graph because it follows properties of bipartite and no two colours are adjacent.
(v1,v4,v6,v7 ) these vertex are with red color
(v2,v3,v5,v8) these vertex are with black color

Option(D) - FALSE
It is not bipartite graph because because V₄ , V₆ and V₈ are adjacent.

In an Hamiltonian Graph (G) with no loops and parallel edges:

According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G. So Statement(i) is True

According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.
So Statement(iii) is True

Statement(ii) :  |E(G)| ≥ 1/2(n – 1) (n – 2) + 2
Any graph with n vertices and at least 1/2 (n−1) (n−2)+2 edges must be hamiltonian.
Refer : https://www.quora.com
Therefore, Statement(ii) is True

So, option (D) is correct.

Given,
Two vertices of degree 4,
One vertex of degree 3,
One vertex of degree 2,
Vertex of degree 1 is unknown,
Now assume k be the number of vertex of degree 1.
Total Number of vertex = 2 + 1 + 1 + k = 2+2+k=k + 4.
Total Number of edges = Total Number of vertex – 1
We now that Total Number of vertex =k+4
= k + 4 – 1
= k + 3
Now Apply handshaking lemma
2 * 4 + 1 * 3 + 1 * 2 + 1 * K = 2 * (Number of edges)
=13 + k = 2 * (k + 3)
k = 7.
Total number of vertex = 7 + 4 = 11.
Hence, option(D) is correct answer.

Concept :
Handshaking Lemma:
In any graph G(V,E) the sum of degrees of all the vertices is equal to the twice of number of edges in that graph

we know that
sum of degrees = 2 * number of edges
n × d = 2 × e

Option(A) : It is not complete graph because there is no edge between vertex A and C, D and B and another thing is number edges is not equal to n*(n-1)/2 edges. If it is complete graph then it must have n * (n – 1) / 2 edges.
Option(B) : This graph is not bipartite. If a graph is 2-colorable then it is bipartite but this graph have more then 2 colors.
Option(C) : According to Dirac's theorem when each vertex has degree at least n/2, the graph is Hamiltonian. For, if a graph meets Dirac's condition, then clearly each pair of vertices has degrees adding to at least n.

So, option(C) is correct

AND OR search algorithm finds goal node at each state in order to reach the final goal state. It works in non-deterministic environment.
A solution for an AND-OR search problem is a subtree that
(1) has a goal node at every leaf
(2) specifies one action at each of its OR nodes
(3) includes every outcome branch at each of its AND nodes

And OR search algorithm works in the following way:
(1) It has to find a solution tree of subtrees.
(2) Solution tree contains the root of the subtrees.
(3) If a non-terminal AND node is in subtree and solution tree then all its children are in solution tree.
(4) If a non-terminal OR node is in subtree and solution tree then exactly one of its children are in solution tree.

AND OR search tree may contain nodes that root identical subtrees (sub problems with identical optimal solutions) which can be unified. When unifiable nodes are merged, search tree becomes a graph and its size becomes smaller.

Determinism : each action has a unique outcome: if chose to drive from
Non-deterministic :Each action has a set of possible outcomes (resulting states) A solution is not a sequence of actions, but a contingency plan, or a strategy: if after pushing the lift button, lift arrives, then take the lift; else take the stairs.

Graph that can be 2-colored are bipartite graph. To check if a given graph is bipartite, we run BFS starting from any node then we check

if there is any edge between two nodes in the same BFS levels the graph is bipartite iff there is no such edge.

A k- coloring of a graph G is mapping f: V(G) -> {set of k elements called colors}, such that adjacent vertices are mapped onto different elements.

A graph is called k – colourable, if it has a k-coloring. A k-coloring of a graph G(V, E) is a partitioning
V = V1 U V2 U V3 ………… U Vk into at most k independent sets of G.

A bipartite graph is a special kind of graph with the following properties-

• A cycle of length n>=3 is – chromatic if n is even and 3- chromatic if n is odd
• A graph is bi- colourable (2- chromatic) if and only if it has no odd cycles.
• A non - empty graph G is bi colourable if and only if G is bipartite.

In an Hamiltonian Graph (G) with no loops and parallel edges:

According to Dirac’s theorem in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G.
So Statement(i) is false

According to Ore’s theorem deg (v) + deg (w) ≥ n if v and w are not connected by an edge is sufficient condition for a graph to be hamiltonian.
So Statement(ii) is True

The maximum number of edges for a graph to be non-hamiltonian is ⁽ⁿ⁻¹⁾C₂+1.
Refer this link : https://math.stackexchange.com/questions/91975/maximum-number-of-edges-in-a-non-hamiltonian-graph

Statement(iii) : E(G) ≥ 1/3(n−1)(n−2) + 2

Consider n=4,

⁴⁻¹C₂ + 1=3+1=4. therefore, if the number of edges is ≤4, then the graph can be non-hamiltonian

E(G) ≥ 1/3(4−1)(4−2)+2 ≥ 4, this says for E(G)≥4 the graph should be hamiltonian, but for E(G)=4 the graph can be non-hamiltonian.

Therefore, Statement(iii) is false.

So, option (D) is correct.

Given graphs are isomorphic if it satisfies the below rules

1. Equal number of vertices.
2. Equal number of edges.
3. Same degree sequence
4. Same number of circuit of particular length

Each node in the above given graph has degree 3 and total number of vertices are 8 and total number of edges are 12.

Option(A) : It is not isomorphic graph because vertex v5 having degree 4

Option(B) :  It is not isomorphic  because vertex v6 having degree 4.

Option(C) :  It is isomorphic  because Every vertex has degree 3 and total no. of edges and vertices are 12 and 8.

Option(D) :  It is not isomorphic  because  Vertex v6 having degree 4.

 Dijkstra’s algorithm : Time Complexity: O(V²)
Case-1:
This case is valid when-

• The given graph G is represented as an adjacency matrix.
• Priority queue Q is represented as an unordered list.
• A[i,j] stores the information about edge (i,j).
• Time taken for selecting i with the smallest dist is O(V).
• For each neighbor of i, time taken for updating dist[j] is O(1) and there will be maximum V neighbors.
• Time taken for each iteration of the loop is O(V) and one vertex is deleted from Q.
• Thus, total time complexity becomes O(V²).

Case-2:
This case is valid when-

• The given graph G is represented as an adjacency list.
• Priority queue Q is represented as a binary heap.
• With adjacency list representation, all vertices of the graph can be traversed using BFS in O(V+E) time.
• In min heap, operations like extract-min and decrease-key value takes O(logV) time.
• So, overall time complexity becomes O(E+V) x O(logV) which is O((E + V) x logV) = O(ElogV)
• This time complexity can be reduced to O(E+VlogV) using Fibonacci heap.

Kruskal’s algorithm  :  Time Complexity: O(ElogE) or O(ElogV). Sorting of edges takes O(ELogE) time. After sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take atmost O(LogV) time. So overall complexity is O(ELogE + ELogV) time. The value of E can be atmost V^2, so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)

 Floyd-Warshall algorithm:The Floyd-Warshall all-pairs shortest path runs in O(n³) time .This is because we have a triple (3) for loop, each with n iterations to make

 Topological sorting: The above algorithm is simply DFS with an extra stack. So time complexity is same as DFS which is O(V+E).

Maximum number of edges in a simple graph
[(n-k)(n-k+1)] / 2
Where, k is the number of connected components(i.e. if graph is connected then k=1)
Given graph is disconnected so we have to take k=2 for maximum number of edges
=[(n-k)(n-k+1)] / 2
=[(n-2)(n-2+1)] / 2
=[(n-1)(n-2)] / 2

We assume k_(n-1) complete graph and other one vertex
So, Maximum number of edges in disconnected graph
=[(n-1)(n-2)] / 2
=[(100-1)(100-2)] / 2
=[(99)*(98)] / 2
=4851

Examples :
Disconnected graph with 2 nodes have 0 edge =[(n-1)(n-2)] / 2= (2-1)(2-2)/2=0
Disconnected graph with 3 nodes have at most 1 edge =[(n-1)(n-2)] / 2=(3-1)(3-2)/2=1
Disconnected graph with 4 nodes have at most 3 edges between 3 nodes and 4^th node as isolated vertex =[(n-1)(n-2)] / 2=(4-1)(4-2)/2=3
Disconnected graph with 5 nodes have at most 6 edges =[(n-1)(n-2)] / 2=(5-1)(5-2)/2=6
In general with n nodes have at most  (n-1)(n-2)/2 edges

Statement(i) : A graph in which there is a unique path between every pair of vertices is a tree.
Above statement is true  because graph can have unique path only when it does not have cycle. If there is no cycles in graph then  it a tree.  A connected acyclic graph is called a tree. In other words, a connected graph with no cycles is called a tree.

Statement(ii) : A connected graph with e = v − 1 is a tree.
Above statement is true  because
Theorem 1 : Suppose |V | = n and |E| = n − 1. The following three statements become equivalent.
(a) G is connected.
(b) G is acyclic.
(c) G is a tree.

Statement(ii) : A connected graph with e=v-1 that has no circuit is a tree.
Above statement is true  because they mentioned e=v-1 means graph is connected it is already discussed statement(ii).A connected graph without any circuit is called a Tree

• A simple graph with n vertices is connected if it has more than (n−1)(n−2) / 2 edges.
• Consider the highest number of edges a graph can have without being connected. It must have two connected components, and, to maximize the number of edges, they must be size n − 1 and 1. To maximize the edges, the large component must be a complete graph, which will have (n − 1)(n − 2)/2 edges.
• Maximum number of edges in a simple graph = [(n-k)(n-k+1)] / 2
• Where, k is the number of connected components(i.e. if graph is connected then k=1)
• If the graph is disconnected then we have to take k=2 for maximum number of edges =[(n-1)(n-2)] / 2
• We assume k_(n-1) complete graph and other one vertex
• So, Maximum number of edges in disconnected graph =[(n-1)(n-2)] / 2

According to Kuratowski's theorem  a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or of K3,3 (complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph).

Refer : https://en.wikipedia.org/wiki/Kuratowski%27s_theorem

• According to the 4-color theorem states that  the vertices of every planar graph can be colored with at most four colors so that no two adjacent vertices receive the same color.
• Every planar graph is four-colorable.

Maximum number of edges in a undirected graph with n nodes ?
In a graph with N vertices we can draw an edge from a vertex to (N−1) vertex like that we will do it for N vertices so total number of edges is N(N−1) now each edge is counted twice so the required maximum number of edges is N(N−1)/2.

Maximum number of edges in a directed graph with n nodes ?
If you have N nodes, there are N - 1 directed edges than can lead from it (going to every other node). Therefore, the maximum number of edges is N * (N - 1).

Alternative :
The maximum number of edges in an n node undirected graph G (n, e) without self-loops is present in a complete graph (Kn):

A complete graph is a graph with N vertices and an edge between every two vertices.

• There are no loops.
• Every 2 vertices share exactly one edge.

We use the symbol K_N for a complete graph with N vertices.
Example : 

Cyclomatic complexity is a software metric. It provides a quantitative measure of the logical complexity of a program.

Cyclomatic complexity provides us with an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once.

Cyclomatic complexity has a foundation in graph theory and is computed in one of three ways.

1. The number of regions correspond to the cyclomatic complexity.
2.  Cyclomatic complexity V(G) for a flow graph G, is defined as, V(G)=E-N+2 where
   E=Number of flow graph edges
   N=Number of flow graph nodes
3. Cyclomatic complexity V(G) for a flow graph G, is defined as, V(G)=P+1 where
   P=Number of predicate nodes contained in flow graph G.

• A spanning tree is a subgraph of the original graph, which connect all the vertexes that where originally connected. This means that removing an edge form a spanning tree, at least a couple of vertexes that were originally connected get disconnected. The definition of spanning tree does not only apply to fully connected graph. When applied to disconnected graph it often takes the name of spanning forest
• Spanning forest is nothing but a set of spanning trees, one for each connected component in the graph
• In the spanning forest the components are represented by a set of edges, rather than a set of vertices. Any vertices in the graph that are entirely unconnected will not appear in the spanning forest.
• When there is only one connected component in your graph, the spanning tree = spanning forest.
• But when there are multiple connected components in your graph. For example in following picture we have 3 connected components
• So for each component, we will have a spanning tree, and all 3 spanning trees will constitute spanning forest
• For an spanning forest of a graph with N vertices and C connected components, Number of edges should be E=(N-C), but in the given graph in the question contains M edges. So to have spanning forest number of edges to be removed
  = M- (N-C)
  = M - N + C

An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices are All of even degree.

Euler Graph :
A given connected graph G is a Euler Graph if and only if all vertices of G are of even degree.
(OR)
An Euler Graph is a connected graph that contains an Euler Circuit.

So option(A) is correct answer


Above graph is a connected graph and all its vertices are of even degree. So, it is an Euler graph.

Alternatively, the above graph contains an Euler circuit BACEDCB, Therefore, it is an Euler graph.

Connect Graph have minimum (n-1) edges and maximum n(n-1)/2 edges

Maximum number of edges in a undirected graph with n nodes ? In a graph with N vertices we can draw an edge from a vertex to (N−1) vertex like that we will do it for N vertices so total number of edges is N(N−1) now each edge is counted twice so the required maximum number of edges is N(N−1)/2.

Maximum number of edges in a directed graph with n nodes ? If you have N nodes, there are N - 1 directed edges than can lead from it (going to every other node). Therefore, the maximum number of edges is N * (N - 1).