DSTL BCS303 ST3 SOLUTION
1(a) Let G = {1,-1, 𝑖, -𝑖} be a group with the operation of ordinary multiplication on G be an
algebraic structure, where 𝑖=√-1.
Determine whether G is abelian.
1.Let G = {1,-1, 𝑖, -𝑖} be a group with the operation of ordinary multiplication on G be an
algebraic structure, where 𝑖=√-1.
1)Determine whether G is abelian.
since all elements in the composition table belong to the set G hence closure property holds
Associative Property holds:
Multiplication of complex numbers is always associative.
Hence associative axiom is true .
Identity element exist:
1∈G
Clearly the identity element is 1 and
. Inverse exist:
From the table,
Inverse of 1 is 1
Inverse of -1 is -1
Inverse of i is -i
Inverse of -i is i
since each element of G has unique inverse, Inverse exist for each element in group
Clearly multiplication of complex number is always commutative.
Hence commutative axiom is true.
Therefore, G is an abelian group under multiplication.
2.Determine the order of each element in G.
To find the order of each element in the multiplicative group G = {1, -1, i, -i}, we need to find
the smallest positive integer n such that g^n = 1, where g is an element of G.
The element 1 has order 1, because 1^n = 1 for any positive integer n.
The element -1 has order 2, because (-1) ^2 = 1.
The element i has order 4, because i^2 = -1 and i^4 = 1.
The element -i has order 4, because (-i)^2 = -1 and (-i)^4 = 1.
3. whether G is a cyclic group, if G is a cyclic group, then determine the generator/generators of
the group G
If Given G is a cyclic group then each element can be generated by i and -i multiplicative group
( i)4=1 ,(i)2=-1,(i)3=-1and i is the element itself hence G=<i> i is the generator of this
multiplicative cyclic group.
Similarly
(-i)2=-1,(-i)4=1,(-i)3=1 and -i is the element itself so G=<-i> so -i is the generator of the
cyclic group
1) b
i) Justify that “The union of any two subgroup of a group (G, *) is not a subgroup of (G,*)”.
Union of two subgroups of a group is not closed with respect to binary operation * hence cannot
be group.
Proof: Let G be an additive group of integers.
Let H1 = { 0, ±2, ±4, ±6, ±8, …..}
and H2 = { 0, ±3, ±6, ±9, ±12, …..}
Here, H1 and H2 are groups w.r.t addition.
Further, H1 and H2 are subsets of G.
H1 and H2 are sub groups of G.
H1 U H2 = { 0, ±2, ±3, ±4, ±6, …..}
Here, H1 U H2 is not closed w.r.t addition.
For ex. 2 , 3 belongs to G
But, 2 + 3 = 5 and 5 does not belongs to H1 U H2 .
Hence, H1 UH2 is not a sub group of G.
ii). Justify that “If a,b are the arbitrary elements of a group G then (ab)2 = a2 b2 if and only if G
is Abelian
2(a) (i). State Ring with example.
The ring is a type of algebraic structure (R, +, .) or (R, *, .) which is used to contain non-empty
set R. Sometimes, we represent R as a ring. It usually contains two binary operations that are
multiplication and addition.
An algebraic system is used to contain a non-empty set R, operation o, and operators (+ or *) on
R such that
(R, 0) will be a semigroup, and (R, *) will be an algebraic group.
The operation o will be said a ring if it is distributive over operator *.
Properties satisfied by Ring .
(ii) State and prove Lagrange’s Theorem.
Lagrange theorem is one of the central theorems of abstract algebra. It states that in group
theory, for any finite group say G, the order of subgroup H of group G divides the order of G.
The order of the group represents the number of elements. This theorem was given by Joseph-
Louis Lagrange.
Proof of Lagrange Statement:
Let H be any subgroup of the order n of a finite group G of order m. Let us consider the cost
breakdown of G related to H.
Now let us consider each coset of aH comprises n different elements.
Suppose, ahi=ahj⇒hi=hj be the cancellation law of G.
Let H = {h1,h2,…,hn}, then ah1,ah2,…,ahn are the n distinct members of aH.
Since G is a finite group, the number of discrete left cosets will also be finite, say p. So, the total
number of elements of all cosets is np which is equal to the total number of elements of G.
Hence, m=np
p = m/n
This shows that n, the order of H, is a divisor of m, the order of the finite group G. We also see
that the index p is also a divisor of the order of the group.
Hence, proved, |G| = |H|
For example if oder of the group is 9 that is no of elements is 9 so the subgroups order will be
1.3 as they are divisor of 9
2(b )What do you mean by coset of subgroup? Find the left and right coset of the given group.
Group is Z and subgroup is H={....,-12,-6,0,6,12, .......} multiple of 6
In group theory, if G is a finite group, and H is a subgroup of G, and if g is an element of G,
then;
gH = { gh: h an element of H } is the left coset of H in G with respect to the element of G
Hg = { hg: h an element of H } is the right coset of H in G with respect to the element of G
What do you mean by Cosets of a subgroup? Consider the group Z of integers under addition and
the subgroup H = {…., -12, -6, 0, 6 12, ……} considering of multiple of 6. Find the Left and
right Cosets of H in Z.
In group theory, if G is a finite group, and H is a subgroup of G, and if g is an element of G,
then;
gH = { gh: h an element of H} is the left coset of H in G with respect to the element of G
And
Hg = { hg: h an element of H } is the right coset of H in G with respect to the element of G.
For the given example Z={.......-3, -2,-1,0,1,2,3....}
H={....,-12,-6,0,6,12, .......}
Hence left COSET 1+H={...., -11, -5,1,7,13....}
Right COSET H+2= {......, -10, -4,2,8,14......}
1 and 2 belongs to Z
Have created left and right coset
3a When is a group said to be cyclic? Prove whether the group (G, +6) where G = { 0,1,2,3,4,5}
is cyclic or not? If yes, then find all the generators.
When is a group said to be cyclic? Prove whether the group (G, + 6) where G = { 0,1,2,3,4,5}
is cyclic or not? If yes, then find all the generators.
A group G is called a cyclic group, if for some a Î G, every element of G is of the form a n, where
n is some integer.
The element a is called the generator of G.
If G is a cyclic group generated by a, it is denoted by G = (a) and the elements of G are in the
form
……………. a-3, a-2, a-1, a0, a1, a2, a3, ………………
Example: The multiplicative group G = {1, -1, i, -i} is cyclic.
We can write G = {i, i2, i3, i4}
\G is cyclic and i is the generator of G.
We can also write G = {-i, (-i)2, (-i)3, (-i)4}, \ -i is also a generator of G
(G, +6) where G = { 0,1,2,3,4,5} is cyclic group. 1 and 5 both are genarator of this group
We can see that
11 = 1 , 12 = 1 + 6 1 = 2
3 2
1 = 1 + 6 1 = 1 +6 2 = 3
1 4 = 1 + 6 1 3 = 1 +6 3 = 4
1 5 = 1 + 6 1 4 = 1 +6 4 = 5
1 6 = 1 + 6 1 5 = 1 +6 5 = 0
Similarly we can check for 5.
3(b )State Group with example. Prove that the set {0,1,2,3,4} is a finite Abelian group of order 5
under addition modulo 5 as composition.
A non-empty set G, (G,*) is called a group if following properties holds
with respect to the binary operation *:
Closure:(a*b) belongs to G for all a*b € G.
Associativity: a*(b*c) = (a*b)*c a, b, c € G.
Identity Element: There exists e€ G such that a*e = e*a = a a
€G
Inverses: a € G there exists a € G such that a*a = a *a = e
-1 -1 -1
4(a). Determine the chromatic number of the following graph.
Solution : The chromatic number of a graph G, denoted as χ(G), is the minimum number of
colors required to color the vertices of a graph G in such a way that no two adjacent vertices
share the same color. Formally, it is the smallest positive integer k for which there exists a
proper vertex coloring with k colors.
Welsh Powell Algorithm consists of following Steps :
Find the degree of each vertex
List the vertices in order of descending degrees.
Colour the first vertex with color 1.
Move down the list and color all the vertices not connected to the coloured vertex, with the
same color.
Repeat step 4 on all uncolored vertices with a new color, in descending order of degrees until
all the vertices are coloured.
By starting with the highest degree, we make sure that the vertex with the highest number of
conflicts can be taken care of as early as possible.
Vertex c b a d e f
Degree 4 4 3 3 3 3
Color red blue green green blue red
So the chromatic number will be 3.
4(b). K4 and Q3 are graphs with the following structures. Which one of the following
statements is TRUE in relation to these graphs. GATE
2015
(i). K4 is planer while Q3 is not.
(ii). Both K4 and Q3 are planar.
(iii). Q3 is planer while K4 is not.
(iv). Neither Q3 and K4 is planar.
5(a). Justify that “In an undirected graph the total number of odd degree vertices is even”.
(b). Justify that “In a graph, the sum of all the degrees of all the vertices is equal to twice the
number of edges”.
5(b). Explain Pigeonhole principle. Find the minimum number of students in a class to
be sure that 4 out of them are born in the same month.
Solution:
Pigeonhole principle : If n pigeonholes are occupied by n+1 or more pigeons, then at least
one pigeonhole is occupied by greater than one pigeon.
4 of them born in same month
There are 12 months in a year
Each month can have 3 students before having 4th student born in that month
Hence 12 x 3 = 36 Students
Now 37th students must be 4th student born on some day
Hence minimum number of students needed are 37 to guarantee that 4 of them were born in
the same month.
6(a). Explain the following terms with suitable example graph representation:
(i). Euler Graph and Hamiltonian Graph.
(ii). Regular Graph.
(iii). Chromatic Number of a graph.
(iv). Walk and path.
(v). Bipartite Graph.
Solution:
(i). Euler Graph
If all the vertices of any connected graph have an even degree, then this type of graph will be
known as the Euler graph. In other words, we can say that an Euler graph is a type of
connected graph which have the Euler circuit. The simple example of Euler graph is
described as follows:
The below graph is a connected graph, and the vertices of this graph contain the even degree.
Hence, we can say that this graph is an Euler graph.
In other words, we can say that this graph is an Euler graph because it has the Euler circuit
as BACEDCB.
Euler Circuit: If there is a connected graph, which has a walk that passes through each and
every edge of the graph only once, then that type of walk will be known as the Euler circuit.
In this walk, the starting vertex and ending vertex must be the same, and this walk can
contain the repeated vertex, but it is not compulsory.
Hamiltonian Graph
The graph will be known as a Hamiltonian graph if there is a closed walk in a connected
graph, which passes each and every vertex of the graph exactly once except the root vertex or
starting vertex. The Hamiltonian walk must not repeat any edge. One more definition of a
Hamiltonian graph says a graph will be known as a Hamiltonian graph if there is a connected
graph, which contains a Hamiltonian circuit.
In the below graph, there is a closed walk ABCDEFA.
Except for the starting vertex, it passed through every vertex of the graph exactly once.
At the time of walk, the edges are not repeating.
Due to all the reasons, we can say that this graph is a Hamiltonian graph.
(ii). Regular Graph: A graph is called regular graph if degree of each vertex is equal. A graph is
called K regular if degree of each vertex in the graph is K. Example: Consider the graph below:
(iii). Chromatic Number of a graph: The chromatic number can be described as the minimum
number of colors required to properly color any graph. In other words, the chromatic number can
be described as a minimum number of colors that are needed to color any graph in such a way
that no two adjacent vertices of a graph will be assigned the same color. Hence, in this graph, the
chromatic number = 3
(iv). Walk –
A walk is a sequence of vertices and edges of a graph i.e. if we traverse a graph then we get a
walk.
Edge and Vertices both can be repeated. Here, 1->2->3->4->2->1->3 is a walk.
Walk can be open or closed.
Open walk- A walk is said to be an open walk if the starting and ending vertices are different
i.e. the origin vertex and terminal vertex are different.
Closed walk- A walk is said to be a closed walk if the starting and ending vertices are
identical i.e. if a walk starts and ends at the same vertex, then it is said to be a closed walk.
In the below example diagram:
1->2->3->4->5->3 is an open walk.
1->2->3->4->5->3->1 is a closed walk.
Path – Vertex not repeated
Edge not repeated
Here 6->8->3->1->2->4 is a Path
(v). Bipartite Graph: If the vertex-set of a graph G can be split into two disjoint sets, V 1 and
V2 , in such a way that each edge in the graph joins a vertex in V 1 to a vertex in V2 , and there
are no edges in G that connect two vertices in V 1 or two vertices in V2 , then the graph G is
called a bipartite graph..
6(b). (i). Define Planer Graph. Is K5 planer or not? Justify your answer with an example graph
representation.
Solution: 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.
The complete graph K5 contains 5 vertices and 10 edges.
Now, for a connected planar graph 3v-e≥6.
Hence, for K5, we have 3 x 5-10=5 (which does not satisfy property 3 because it must be
greater than or equal to 6).
Thus, K5 is a non-planar graph( Kuratowski Case I).
Theorem: A complete graph of 5 vertices is non planer.
(ii). Define Isomorphic graphs. Are the two given graphs isomorphic? Justify your answer.
Solution: Two graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic if there is an injective (one-
to-one) and surjective (onto) function f from V1 to V2 with the property that a and b are adjacent
in G1 if and only if f (a) and f (b) are adjacent in G2, for all a and b in V1. Such a function f is
called an isomorphism.
In short, out of the two isomorphic graphs, one is a tweaked version of the other. An unlabelled
graph also can be thought of as an isomorphic graph.
If G1 ≅ G2 then −
1. |V(G1)| = |V(G2)|
2. |E(G1)| = |E(G2)|
3. Degree sequences of G1 and G2 are the same.
4. If the vertices {V1, V2, ...Vk} form a cycle of length k in G1, then the vertices {f(V1),
f(V2),… f(Vk)} should form a cycle of length k in G2.
The given graphs are not isomorphic.
1. |V(G1)| = |V(G2)|=5
2. |E(G1)| = |E(G2)| = 5
3. Degree sequences of G1 and G2 are not same. The graph on the right contains a vertex of
degree 4, while the graph on the left does not.
