Page 1

Question 1

Graph

Answer 1

• tripple (Vg, Eg, Rg)
• Vg set of vert
• Eg set of edges
• Rg function associates each edge to unordered pair of vert. Called endpoints of edge

Question 2

Graph is finite

Answer 2

• If sets Vg vert and Eg edges are finite

Question 3

3 types

Answer 3

• 2 edges common vert poin, adjacent
• 2 endpoints edge same, loop
• more than one edge joins 2 vert, multiple edges

Question 4

Simple graph

Answer 4

• No loops, no multiple edges

Question 5

Edge

Answer 5

• subset of 2 elements in Vg

Question 6

Subgraph

Answer 6

• G’ = (v’,e’,r’) if V’ in V, e’ in E and r’(e) = r(e) Ae in E’

Question 7

Full/Induced subgraph

Answer 7

• for every u and v in V’
• if e is a edge with endpoint u and v in G
• then e also edge in G’

Question 8

Proper Subgraph

Answer 8

• v’!=v

- E’ != E

Question 9

Complete Graph

Answer 9

• edge between any 2 vert

- (Kn) (K choose n) n(n-1)/2 edges

Question 10

Null Graph

Answer 10

• No edges (bunch of dots)

Question 11

Bipartite

Answer 11

• if there is a partition of V into 2 disjoint sets X Y
• any edge has 1 endpoint in X and 1 endpoint in Y
• V = XUY in a bipartition of G

Question 12

Complete Bipartite

Answer 12

• Bipartite graph whose bipartition XUY is st every vert in X is adjacent to every vert in Y
• V(Km,n) = m +n
• E(Km,n) = nm

Question 13

Isomorphism

Answer 13

• Isomorphism F: G ->G’
• pair of bijective functions Fv: V -> V’ Fe: E ->E’
• st e in E joins u and v iff fe(e) joins fv(u) and fv(v)
• G =~G’
• same number of edges, same degree sequence (converse false)

Question 14

Bijecton

Answer 14

• Injective A x,y in X then if f(x) = f(y) then x=y

- Surjective Ay in Y, E x in X st f(x) = y

Question 15

Complement

Answer 15

• simple graph Gc
• same vertex set Vgc = Vg
• for distinct u v in V, u and v adjacent iff not adj in Gc
• Gcc= G
• H=~G Hc=~Gc

Question 16

Degree

Answer 16

• d(v) of a vertex is the number of edges incident with v

- loops counting twice

Question 17

Isolated vertext

Answer 17

Degree d(v) = 0

Question 18

Degree sequences

Answer 18

• listing degrees of vert in non-decreasing order

- allowing repetitions

Question 19

Regular

Answer 19

• K regular, all vert degree k

Question 20

Degree sum Formula

Answer 20

• Sum di = 2E(g)

- graphic if degree sum formula is even

Question 21

Graphic sequence

Answer 21

• list of int which is the degree sequence of a simple graph
• degree sequence d = (d1……dn) graphic iff d’ graphic
• d’ removing dn entry and subtracting 1 from next largest element (reordering if needed)

Question 22

Vertex transitive

Answer 22

• Looks the same whatever vertex

- for any u and v in V there is an automorphism a of G with a(u) = v

Question 23

If Graph is vert transitive then also

Answer 23

1) Graph G is regular

2) G simple, Comp Gc is vertex transitive

Question 24

Walk/Edge sequence

Answer 24

• finite alternating seq of vert and edges V0E1V1,E2….E