UNIT2-RULES OF INFERENCE

Valid
Arguments-consider statement
·
a

(p 1 p21p3
,
...
1pn) -
q

Pl P2,
, ..., po are called the
premises of the
argument
is called the conclusion
q .

This
argument is called a valid
argument if when Ps P2
, , Ps ..., Pn one true

be
then , a should also true.

Logical Implication If p and of arbitary statements such that is

·
are
pzg
-

a
tautology ,
then we
say
that
plogically implies q
p=q

Rules valid , to
of Inference-in order to that an
argument is need
·

prov we

consider those values that bo to check whither

only of Pi , P2 , ..., po are

P11P21 ...
>
pn- q is a
tautology

as it is true in all other cases otherwise .

The list
of techniques that allow
far this
simplification is called ruls
of
inference .

First check
if the valid
using basic and
>
statements are
logic
-

truth value
verification .

declone it invalid statement

If
> then
not
-

as an .

again using ruls

of inference
>
Otherwise ,
-

prom so once .
# p
=r Premise 1

r- S Premise 2

tv US Premise 3

- + yu Premise 4
~ u Premise 5

~
p Conclusion

By Premise E, we is true .

.. U is
false

In premise 4, utXU is true ,

u is
false
:. ut is Gree ,
thus t is
false
In premise 3,
if t is
false and Vas is true
,
then as is true

.. s is
false .

Since s is
false ,
r also has to be
false .

is
Since r
false ,
then
p
is also
false .

up is true .

:
[(p + r)1 (res) +(tvas)1(u + vu)1 vo] > up
-

When all premises are truse

,
the value
of the conclusion is

up ,
which is (Fo) =
To
Thus
,
the
argument is a
logical implication and is thus valid.

Using the other method ,

=r Premise 1
I
p
2 ↑7 s Premise 2

3 +VuS Premise 3

4 u + XU Premise 4
5 vu Premise 5

6p - s ① and Q and low

of syllogism
- turs Esut commutative law
.
8 S-t

9 .
p-t and O and law
of syllogism
10 . > U
-
and
logical implication
11

12
.

ptu and and lawof syllogisma

up

Thus it is valid
,
a
argument .

* p tr Premise

up - q Premise 2

- s Premise 3
q

All
premises ore true always
.

1 .

p -r
2 .
up - g
3 -
.

9 S

4 . ur -
up By rule
of contrapositive D and ②
② law
and
of syllogism
5 ur +
.

q
⑤ and ③ law
of syllogism
6 ur+s .
.

*. p- q Premise 1

Premise
g - (MNS)
2
.
2

. ury(n +
3 Vu) Premise 3

4 .
Put Premise 4

If I is true ,
then , PET, and t To

If
② is true
, then To

If ② is true , MASTo
,
rTo and s To
um v(ut vu) To
~
To V(uTj vU) = To
Fo VFj Vu To
Naturally i is To
,
 given implication is
Thus the tautology a
,
.
By proving through laws
of inference ,

① and Q
5 .
p-(Mns) and law
of syllogism
6 .
P ④ and Rule
of conjuctive simplification
7 . MAS ⑤ and O and modus
pomens .

⑦
8 .
M and
conjuctive simpl
9 r- cu + vu) ③ and implic .
.

⑨
logical
10 Ut Vu modus
.

posens
④
Ganjucusimply agism.
11 .
E and

12 ( and

(pvq) + (xS) Premise 1

2 .
r> - t Premise 2

3
. Ut Premise 3
trur .
All premises ore
From premise ,
utTo ,
tEFo

From ② ret
,
r+ Fo ,
MFo
,

③, (Mxs) To
From
(upveq) >
-

(upvug) - (fons) = To

Cup Vrg)
>
fo To
-

upvog Fo
To
up) Fo, pet
uq Fo
, g To

Proving by rules
of inference ,
4
. Ur ② and ③ modus tollens
UrVus
S .

disjunctive amplification.
s .

vrunsevr(p1g)) ① De Margan's law and contrapositive

⑥ modus
7 .
paq posens
8 .
P ⑦ conjuctive simplification .
 Ex -
upt q Premise I

q
- r Premise 2

ur Premise 3

All premises are considered to be equivalent to

To.
urTo (From O
.. r Fo

(q - r) To (From Q

g- F-
) To

.. Fo

up- q ( To (From

(p- q)n(q rp) To +

( p Fo) x(Fotup) # To
+

=> )
up- Fo To

up Fo
: To

Using rubs
of inference ,

4 .
(p-q) +
(q -up) ① biconditional simplification
5
. ur -
>
ug ② and contrapositive .

6 .

uq ③ and ⑤ and modus posens

④ and
up g conjuctive
7 -
.
simpl .

⑦
8 .
uq
-
p and contrapositive
9
P
⑥ and $ modus
.

poruns .

# u=r

(Mxs) >
-

(pvt)
q
- (uns)
ut

Conclusion
, g tp
q (Additional premise)
q To

> (uns) To
&
-
 uXsTo : U To

ut to t Fo
,

u =
r To
.. r To
(MNs) -(put) To
To >
(pVt)To
-

>
put To
pVFj)To
:. pTo

ruls
using of inference ,

suns and modus

pomens
7
. U ⑥ conjuctive simplification
.
8 M
① and Q modus
ponens
9
. S ⑥ conjuctive simplification
Ms and⑨
10 .
conjunction
② and modus
put powers
12 . tup commutative
13 .
Ut- p.
14 .
p
and modus
powens.

-
 UNIT2-QUANTIFIERS

open statement it
A is
Open Statement declarative statement
if
·
-
an

. Contains
1 one or more variables

2
. is not a statement

statement when the variables it are artain

.
3 becomes a in
replaced by
allowable choices .

Universe Discourse
of From point of above, these allowable choices constitute
· -
3

called universe universe discourse

What is the or
of .

An open statement is
represented as p(x) ,
r(x) , etc.

open statement with than variable is

An more one
represented as
qbc y).
,

the the statement

The statement
up(x) is
negation of p(x).

quantifiers-quantifiers used to describe the universe

far
·
one an
open
statement, which it evaluates to true.
for
It has two
types-existential and universal .

Existential
Universal
rufers to the idea

idea
of 'far some x'
,
Ex.

to the x' Voc

rufers of 'far all
,
.

p(x) has variable. The

Bound Variables
open statement
Free and An
·
-
a

the statement the

truth value
of depends on the value
a
of all our

universe . This variable is called a

free variable.

A variable with is variable

associated a
quantifier called a bound .

Vap(a) is true , then Expla) is true.

NOTE
If also always
-

the is the the implication,

If converse
of an
implication same as

then the two open statements an biconditional.

For two statements r() and S(x) then
,
·

open ,

=
[r(x1S()] # Exr(x) 1 7xS(x)

as ExM(x)1 F xS(y) => Jx[M(x)1S((()]

However Expoqu] Expan =xg(x)

by the rube
of conjuctive simplification
Similarly ,

In case
of multiple quantifiers we read
quantifiers from left to
·

right .

that element
Method of Exhaustion
Exhaustively listing and
proving each
· -

in the universe
satisfies the required condition is called method of
exhaustion. This method is used
only when the universe is
fairly small.
·
Rule of Universal specification -

If an
open statement becomes true
for
all numbers in then
replacements by the a
given universe ,
that open

statement is true
for each specific individual member in that universe .

universe
If p(c) is an
open
statement
for a
given and
if
#xp(x) is true , then pla) is true
for each a in the universe.

Rule Universal Generalization If open statement p(x) is proved

of
·
-
an

so be true when a is replaced by any artitarily from chosen element c

our universe ,
then the
universally quantified statementH o plac is trur .

Furthermore , the rule extends

beyond single variable
a
If have .
we

is proved to and
open statement q )
an that ,
be true when x

y are replaced by arbitrarily

elements
from the chosen
universe same

or their own respective universes then the universally quantified,

statement
HsHyg(x y) is true Similar results hold for the cases
, .

three variables.
of or more

·
Rule of Existential Specification -
Consider a statement Exup(x).
existential states that specified
The rule
of specification this statement can be

is element the universe is true.

as upcal where a an
from for which spec

is
Rule of Existential
Generalization-conventing up(a) to
Exup() called
·

the rule
of existential
generalization .
* write the converse , contrapositive and inverse of Fx[s(x) > r()] -

Converse ,
Vx
[r(x) >
-

S(x)] Truth value -

False

Inverse
,
(x
[us() + ur(x)] Truth value -
False

Contrapositive Xx(ur(3rs(x)]
,
Truth value -
True

conclusion -

#x[s(s) +
r(x] #)
Vx[urix) >
-

vskd]

Similarly ,
Her [r(x) > S(x] =
-
V [us() > -
ur(x)]

~
[fxs(x)] >
Ex-S(x)
~ [ = xs()] = Hxus(x

E Chis
Negate and
simplify v
[Fx (px q()] >
-

= xv[p(x) + q(x)]

=
x[p(x) nuq(x)]

# Hx[p(x)vg(x)]
Hx(w( p(x)ng(x)
>
-
r(x)]
Hx ur(x) > -

p(x)

Using universal specification,

=
#x p(x)xg(x) p()1g()
Yx[to(p(c) 1 g(x) M(x] >
- =
Topk)1gk] >
-
r(x)

p(x)vg(x)
r(x)
p(x)ng(x)
~ >
-

ur(x) >
-

~[up(x)1g()] contrapositive
vr(x) >
-
[p(x)vug()] DeMorgan's theorem .
 vr(c)#
To Assumed promise
p(x) Vug(c) Modus
pomens
p(x) v g(x)
p(x)v[ug(x)1g(x)] Distributive Law

p(x)
~ M(x) >
-
p(x)

# vr(c) Pl

Y+
(p(t) q( -) - +
P2

Y (q(t) -
+
> M(+
)] P3

up(c)

Using universal specification,

ur(c) PI

p(c)> q(c)
-
P2

q(c)-r(c) P3

ur(c) is Grue

r(c) is false
r() To
g() >
-

g() FjTo
>
-

:.

g(c) Fo
p() >
-
q()) To
p(c) >
- > To
Fo

:
p() Fo

Thus,
proving using rull
of informa
ur(c)

p(c) ->
q()
g() r(c)>
-

p(c)-r(c) ② and law

of syllogism
up(( ④ and Q Modus tollens .
E Hx(p(x)vq(x)] PI

Yx[rp(x)xq(x)) >
-
M(x)] P2

Hxvr(x) Assumed P3

Using universal specification

1 p(c)Xq(c)
2
[up(c)Xq(c)] - r(x)
3 ur(c)

~ M(c) To
. MIC) Fo

[rp(c)xqx] >
- M() To

[up(c)Xq(k] >
- Fo) To
= Fo
:
up(c)1g()

p() vg() To

:
p(c) # To , g(l) can be to are Fo

..
using rules
of inference .

(p(c)vq()
2
[up(c)xq(c)] - r()
3
vr(c)
4
-[0p()xq()] ② and & Modus tollen
④
5
p(c)vwq() Demorgan's theorem
O and LAS
6 .

p(c)V(q()Xvq()] of distribute law

7 .
p(c)

8 .
vr() >
-
p(c)
Ho [vresepad] ⑧
9 .
universal
generalization
 ① ② ③
① +
E pq M S
gar
O
visum)
I
p

O
O
!
O 0 O

8 00 I O I O

00 8 00 O

00
! 10 O
I

I O

00 8 O I O

, · j
0
O
↓ I

"
O

O 11

"
0

o ! 81
0
0
O
O

o O
I
W
!
I

19 !
O O O

! O 8 O

Truth table
for (pxq)x(up - r)

p q r peq uper peq1uper

O O O I O O

00 I I I

! G

%
O

" I I

10 O I O

10 O O

10

I
! I
I

↓
! !

(g(r) (pEsq) r
(a)
Pts(q(r)
E Poog
M

G
S I O

·
00 O

0 10 O I O

01 I
I O O
 I
100 I O O
O

o
!
O I
O

I I
! !

Eu[(p -q)x(q ) +p >

v(p + g)vv(g + p)
(px(q)v(gN-p)

I (vp/vq)v(Toxp) Xp
(up yug)x(Toup)xp
(upveg) x
Toxp
(upvrq)xp
(rpxp)v(vq/p)
vqXP/

# (p + q) Premise

(gar) -s Premise 2

M Premises

P Premise 4

p is true
r is true
is true
q
S is true

using laws
of inference ,
5 .

G ①
① modus ponen
6 .

gar
③ ③ conjuction
7 . S
⑧ ② modus
porun
UNIT 3-SET THEORY

collection
of well-defined objects These
objects said to be elements
·

sets-sets are a . are

the
or members
of set.

Capital letters represent the set whereas small letters represent the elements

the
of .
set

Universe
of Discourse-I the valid of numbers (integers rational
·

denotes set ,
no S
, .

etc. ) valid
for which the set is .

Cardinality of a Set-for
given set A, IAI denotes the number
of elements in
·

any
the
A and is
referred to as
cardinality or size
of the set A

subsets and Proper Subsets

If sets
from universe & that is
·
C and D C
say
are a we
-

subset and write CED , element element of in addition

a
of D
if every of > is an D.
If
then
D contains an element that is not in c
,
C is called a
proper subset of D .

CID subset

CCD Proper subset

C(D = CED

CED # CCD

al said to
Equal Sets For
given universe the sets C and be equal
·
-
a D are
,
CFD
,

When C&D and D&C

.

Repitition elements has consider unique elements in

of no
effect . We
only the set .

Based on this idea ,

CCDCED N CFD

·
Basic Theorems on Sets -

1 .
ALB ,
BIC then AC .

2 .
ACB
,
BEC then ACC

3
.
If AEB , BCC then ACC .

4.
If ACB , BCC
,
then ACC .
 Null Set-The will set elements It
emply is the (unique) containing
·
or set set no .

is dinoted
by 0

9 +
203

Power universe set &(A)

Set-If A is set
from M the
of denoted is
·
a
, power A ,

corset)
the collection of all subsets
of A
.

If the
cardinality of the original set is n ,
then the
cardinality of its power

set is 21

in both not considered in union

Elements repeated sets are the
of sets .

n + 1nn
I
+
M M r - 1

No .
of subsets
of odd cardinality = No ,
of subsets
of even
cardinality
UNIT 3 - RELATIONS

·
Cartesian Product -
For sets A and B
,
the Cartesian product or cross product
of A and B is denoted
by AXB and equals S(9 b) , a EA ,
Je B3

AXB = 1AI IBI

.

1AXB1 /BXAl
= but not
necessarily AXB = BXA

The Cartesian be extended two

definition of a
product can to more than sets .

↑ XAzX ... An =
Sla ,
92 , ...,
an) , aieA , Iin3
These elements called
are
generally n-tuples.

Cartesian products can also be represented as a true .

A =
52 , 3, 43
(2 , 4)
B =
24 53 ,
4 -

AXB 5 - (2 , 5)
4 -
(3, 4)
3

5 -
(3 , 5)
4 - (4 , 4)
4
5 -
(4 , 5)

Binary relation For sets A,B subset

of AXB is called
binary
·
a
amy
-

called relation
relation
from A to B .

Any subset
of AxA is a
binary on

emn relations
For
finite sets A,B with 1A1 = m and IBI = n
,
there are
from A

to B
P rulation the rulation itself
including the
empty as well as AxB .

Infix Notation Relation said

of If R is relation , the
infix notation is
·
a a
-

to be
<Ry and a Rs .

·
Ax =

&xA Q
·
=
·
Ax(B1c) =
(AXB)n(Ax()
·

Ax (BUC) =
1AXB) U(AX()
·

(A1B) xc =
(Ax() n(BX)
·

(AUB) x1 = (AXC) U(BX()

Reflexive Relation A relation R set A is called

reflexive if for all CEA
·
-
on a
,

(x, x) ER .

Relation-Relation y)
symmetric R set A is called
symmetric if (x , ER then
·

on a
,

x) Er
(y ,
for all x,
y
EA
.

is called
Transitive Relation For set A a relation Ron A transitive
if far all
·
a
-

z) ER , implies
x ,
y ,
z
,
EA
,
(a) ,
y)(y , it (5 , z) ER .

Antisymmetric Relation-Givn relation R set A R is called

antisymmetric
·
a on a ,

if for all a beA ARS and GRa implies that a 6

=
, ,
.

Its not the same as

reflexive as not all Ca , a) is required to be in the

set .

·
Partial Order Relation -
A relation R on a set A is called a
partial order or
pa-
transitive .
rtial
ordering relation if R is
reflexive , antisymmetric and

relations
To
find of partial
the number order on a set that comprises
of positive integr divisors
of a number in

aproductofpowerofprima
Represent thenumber as
·

some limit on its value.

EX - 12 = 22 3 .

c = 2434 ,
d = 2P 3 . where (c , d) ER .

0xm = p = 2
, okn(q)

Apply the
formula for combination with repetition and rule
·

use

of product .
·

Equivalence Relation An equivalence relation -

R on a set A is a relation that

is
rylexive symmetric and transitive
,
.

the largest
For
any given finite set A
,
AxA is equivalence relation on

A and the
equality relation (ai , ai) is the smallest equivalence rula-

tion .

Partition-Given set A and index set let Ai Aid far each it I

. Then
·
a an I A
, ,

SAiSitI is a
partition of A
if

a) A
=UA
i and AjlAj = far all i,
jtI where i

Each subset Ai is called a all or block

of the partition . Each element
of A will

to
belong only one all in the partition .

Equivalence Class-let R be an equivalence relation on a set A .

For each CEA
,

the equivalence class

of x
,
denoted
by [x] is defined by [x] =

S YEA yRx],

Theorem If R is an equivalence relation on a set A and , EA then

·

y
-

>
- x[x]

xRy if and only if [x] (y]

- =

[x]
(y] <x]1(y] 0
>
- =
or =

The distinct equivalence classes

of R provide us with a
partition of A
.

a
types of questions-Given a set A and an equivalence relation , determine

the partition.
Givm a set A and the
partition ,
determine the equivalence rulation.

Union
of cross products

each partition

induces
any equivalence
relation
Theorem-If A is set , then R A
·
a on

a partition on A and
any partition on A gives rise to an equivalence
relation R on A
.

There is also a one-to-one correspondance . Each partition has

equivalence relation vice

exactly one and versa.

Number
of Equivalence Relations-we
stirling numbers .
If there
·
use

are n elements,

Sin ,
is no,
of equivalence relations
UNIT 3 -
FUNCTIONS

f(a) 6 when a,b is ordered pairs in the

function f
=
an

G is called the
image of a under
f and a is called the
preimage .

associated
Each element a is
uniquely implying that a cannot be mapped
10 2 separate values
of .
6
 distinct objects split
Onto
functions represent the Scenario where m are

distinct containers.
amongst in

If min
,
there are no such
functions .
 objects
This represents
m distinct 1 into n identical containers.

Emp dustion = No ,

of unordered
factorizations
me distribute distinct
counts the no ,

of ways to n
objects
distinct containers.
among
in
function composition may not be commutative but is associative .
UNIT 4 :
GROUP THEORY

boa is called abelian

If aob =

for all a ,
bEG ,
thin G a commutative or
group .

(G , 0) is and r , nezt with and then

If any group 133 1rXn
·

19 0920930
,
....
oar)o(am +10 ....
oan) =
9, 0920 .... roarto ... an

all .
G
where
they are elements
of

abelian group
·
(Zn +)
,
is the
of all
integers from o to n-1 under the modulo operation
(a + b) % n

(Zp*, ) is the Abelian

group with elements from 1 to n-1 defined with the modulo

operation .

↑
Imp not all elements the those that
, of En have to be part of group . Only
satisfy the
required property one included .

unique inverse will at When it is

The
of a be
designated by .
written additively
,
additive inverse
a is used to denote the
of a
-

element and G
The
identity itself are said to be trivial
subgroups of G
.

All others are termed non-trivial

as or
proper.

If finite only ,
check this
condition
 n-sized
Given
symmetric of polyon,
·

a
group
Sn =
(to ,
A, ...,
An , Mo ,
r, . - . Mn)

Each element is represented as 0 . -- on

y ,
ye ....
Yo

elements and leaves the

To
find an element
of order n , swap n
first rust .

Sj ,
n =
2

An element can be

12345

21345

The it is
cyclic group generates
1234512345

1234321345

consider
group zn
·
a

do
It will have elements
from o n -1

It is addition modulo 40
a
group .

The order the element is element p that

of of the
group an such

.a
p
= O(mod40)

If we
find an element whose order is equal to the size
of the
group
,
then the

is
group cyclic .

In
cyclic group of order
any
n
,
far each divisor d
of n Chie are

exactly (d) elements of order d.

UNIT V-GRAPH THEORY

E(G)
Graph-A graph is triple consisting of Vertex set VC2)
edge set
> G an
-

a a
,

and a rulation that associates with each

edge two vertices (not
necessarily
distinct) called its endpoints .

>
-
Loop -
A loop is an
edge whose endpoints are
equal.

>
-
Multiple edges -

Multiple edges are

edges having the same pair of endpoints.

>
-
simple graph-A simple graph is a
graph having no
loops or
multiple edges
. We

unordered edge
treat the edge set as an set
of vertices ov or u
for an e with

endpoints u and .
V

and endpoints of
>
-
Adjaunt and
neighbour vertices-when u are the an
edge they ,
are

adjacent and are

neighbours .

>
-
subgraphs - A
graph G' =
(VE) is a
subgraph of G = (V , E)
if VIV and E'FE .
G' is

said to be contained in G
,
denoted
by GIG .

>
- connected -
A graph is connected
if ,
far every pair of Vertices Chr ,
is a path
i . e ,
a
sequences of edges ,
between them that belong to the graph .
Otherwise,

it is disconnected.

Null has
graph-A graph edges but than untex.
>
-
with no more one

>
-
Clique-A dique
-
in a
graph is a set of pairwise adjacent untices ,
ie . a

complete subgraph .

>
-
Independent
-
set -
An independent set is a subset
of vertices with no
adjaunt
pairs ,

the
>
-
Bipartite graph -
A bipartite graph is
disjoint union of two independent sets.
Union
of two disjoint independent sets called the partite sets
of .
G
>
-

complement-the complement 5 of a simple graph G is the simple graph with

VCG) UVEECE) UVECG).
the Vertex set
defined by if and
only if
cliques become independent sets and vice versa with the complement of a

graph .

A
graph can be self-complementory

>
-
colouring of a graph-A colouring of a
graph is partition of a a set into

independent sets with no two adjacent ,

untices
having the same colour .

Number The chromatic number X(G) is the minimum

Chromatic
of graph
>
- -
a

needed label that

adjacent vertices recieve
no .

of colours to the vertices so

VCC) be
different colours. A
graph is -partite if can
expressed as the

union
a
of (possibly empty) independent sets.

incident with counted

>
-
Degree-The number
of edges on a vertex vi ,
self-loops
twice ,
is called the
degree d(vi) of vertex Vi.

deg(vi) = ze

The number
of vertices
of odd degree is always .
even

-
Regular Graph-A graph in which all vertices are of equal degree is

called
regular graph.
a

Isolated and Vertex-Untex isolated untex Vertex

pendant of degree is
>
-
o an .

of degree I is a
pendant vertex.

the matrix whose

>
Adjacency matrix-the
adjacency Matrix written
by AlG) is
-

, ,

(i , j) entry is the no
of edges with
.
endpoints as vertices ; and j.
It is always symmetric .

Matrix-The incidence Matrix written M(G)

>
- Incidence
of G
,
is the
n-by-m
with vertices edges , j)
untex i
matrix , n and m whose (i
entry is I
if
is the
endpoint of edge j ,
otherwise 0
.

>
-
[somorphism-An isomorphism from a
simple graph G to a simple graph
A is a
bijection fi VCG) -V(H) such that
every edge ur
of G is mapped to
 denoted
the
edge flu)f(v) of H . We then
say
2 and n are isomorphic ,
by
GEN .

To prov a
graph is not isomorphic ,
there are
many ways-
not the same
list
of degrees is
·

No do carrespond etc.
of edges not
·
,
,

Isomorphism is equivalence relation which that split the

·
an means we can

into classes , called isomorphism .

classes
graph equivalence

>
-
complete Graph-Graphs with n untices and (2) edges
.

complete bipartite graphs are bipartite graphs where each element of one

other
independent set is mapped to each element of the independent set
.

- Important .

Decomposition list of subgrap

decomposition is
>
-
A
of a
graph a
-

hs in which
every edge appears exactly once .

A
graph G is
self-complementory if and only if the complete graph
is a decomposition into two
copies of .
G

Peterson's Peterson's 10-vertices with

>
-
Graph-The graph is a
graph
15
edges
12
>
- Two non-adjaunt untices have

45 exactly
one ventex that they
33 34 share
13
.

52
>
-
The
graph has no triangle ,

but is not
bipartite .

4
shortest in the
42
- The
cycle
Peterson's graph has length 5
.
IS
23
>
-
Path-A path
is a simple graph whose vertices can be ordered so that

two untias are adjaunt if and

only if they are consecutive in the

list .

with
-
Cycle-A cycle is a
graph equal no ·

of untices and ed

ges with a walk

starting from one untex ending at the same

untex without repeating an

.
edge
>
-
subgraph
-
A subgraph of a
graph G is a
I
graph that

VIH) - V(G) and EIH) [ECG) and the assignment of endpoints

H is the same as a
in
to in
edges

that be created with M

· The number
of graphs can

vertices an 2).
pairwise ,
vertices can be chosen in ways
and each

have the choice to exist not Thus

,
of these edges or .

2(c)