1.2 NOTATION , AN D A CATALOG

This can be thought o f as a

disconnected grap h wit h 9

vertices, o r a s two separat e

connected graphs .

Any grap h i s just a collectio n o f connected graphs ; thes e ar e calle d th e compo -

nent s o f th e graph .

The graph s w e have bee n studyin g ar e presente d a s drawing s o n paper . I t

is eas y t o inven t graph s whic h ar e describe d i n othe r ways . Fo r example , w e

can mak e a grap h whos e vertice s ar e al l o f th e tenni s player s i n th e world , an d

where a n edge connects tw o players if they hav e played tennis together. W e hav e

defined a graph , althoug h i t woul d no t b e feasibl e t o actuall y dra w it . Anothe r

graph ca n b e mad e b y lettin g th e vertice s b e th e countrie s o f th e world , an d

having a n edg e connect tw o countries i f those countrie s borde r eac h other . Wit h

the hel p o f a ma p i t woul d b e possibl e t o dra w thi s graph . I t i s amusin g t o

invent fancifu l graph s an d the n tr y t o determin e what propertie s they have . Fo r

example, i s th e tenni s playe r grap h connected ? I f i t is , tha t woul d mea n eac h

tennis playe r ha s playe d someon e wh o ha s playe d someon e wh o has . . . playe d

Jimmy Connors . Th e pla y Six Degrees of Separation mentions , informally , th e

graph whos e vertice s ar e al l o f th e peopl e i n th e world , wit h edge s connectin g

people wh o kno w each other . Th e titl e o f th e pla y come s from speculatio n tha t

you can ge t fro m an y one vertex to any other verte x b y crossing at mos t 6 edges.

In orde r t o mak e a n organize d stud y o f graphs, w e must impar t a fe w mor e

rules. Usuall y we do not allo w our graphs to have more than one edge connectin g

two vertices , an d w e do no t allo w a n edg e t o connec t a verte x t o itself .

A graph with

multiple edges

A graph with loop s

Unless we state otherwise , a 'graph' i s a 'grap h withou t loop s or multipl e edges.*

We classif y graph s accordin g t o ho w man y vertice s the y have . Her e i s a