1
Q
Graph
A
- 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
2
Q
Graph is finite
A
- If sets Vg vert and Eg edges are finite
3
Q
3 types
A
- 2 edges common vert poin, adjacent
- 2 endpoints edge same, loop
- more than one edge joins 2 vert, multiple edges
4
Q
Simple graph
A
- No loops, no multiple edges
5
Q
Edge
A
- subset of 2 elements in Vg
6
Q
Subgraph
A
- G’ = (v’,e’,r’) if V’ in V, e’ in E and r’(e) = r(e) Ae in E’
7
Q
Full/Induced subgraph
A
- 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’
8
Q
Proper Subgraph
A
- v’!=v
- E’ != E
9
Q
Complete Graph
A
- edge between any 2 vert
- (Kn) (K choose n) n(n-1)/2 edges
10
Q
Null Graph
A
- No edges (bunch of dots)
11
Q
Bipartite
A
- 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
12
Q
Complete Bipartite
A
- 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
13
Q
Isomorphism
A
- 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)
14
Q
Bijecton
A
- 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
15
Q
Complement
A
- 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
16
Q
Degree
A
- d(v) of a vertex is the number of edges incident with v
- loops counting twice
17
Q
Isolated vertext
A
Degree d(v) = 0
18
Q
Degree sequences
A
- listing degrees of vert in non-decreasing order
- allowing repetitions
19
Q
Regular
A
- K regular, all vert degree k
20
Q
Degree sum Formula
A
- Sum di = 2E(g)
- graphic if degree sum formula is even
21
Q
Graphic sequence
A
- 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)
22
Q
Vertex transitive
A
- Looks the same whatever vertex
- for any u and v in V there is an automorphism a of G with a(u) = v
23
Q
If Graph is vert transitive then also
A
1) Graph G is regular
2) G simple, Comp Gc is vertex transitive
24
Q
Walk/Edge sequence
A
- finite alternating seq of vert and edges V0E1V1,E2….E
Graph Theory
flashcards
Decks in class (1)
# Cards
