# Chapter 3: Connectivity and Paths Flashcards

1
Q

A
2
Q

Vertex/Edge Relationship with Connected Components

A
3
Q

Connected Graph on n vertices has how many edges?

A
4
Q

Euler’s Theorem (Eulerian Graph)

A
5
Q

All degrees even means what for maximal trails?

A
6
Q

Semi-Eulerian Condition

A
7
Q

Fleury’s Algorithm

A
8
Q

Hamiltonian Cycle Relationship with connected components

A
9
Q

Hamiltonian and Bipartite implies

A
10
Q

Dirac’s Theorem

A
11
Q

Ore’s Theorem

A
12
Q

Tree Leaf Facts

A
13
Q

Edges in a cycle are not…

A
14
Q

Characterisation of Trees with n vertices

A
15
Q

Tree/Path Condition

A
16
Q

Tree More Facts

A
17
Q

Prüfer Code Facts

A
18
Q

Cayley’s Theorem, 1889

A
19
Q

Matching/Augmenting Path Relationship

A
20
Q

Berge, 1957

A
21
Q

Hall’s Theorem

A
22
Q

k-regular, Bipartite implies

A
23
Q

Corollary 1.12 (Bipartite, Neighbourhood, Cardinality)

A
24
Q

1-Factor Facts

A
25
Q

Tutte 1947

A
26
Q

Bipartite perfect matching decomposition condition

A
27
Q

Which complete graphs are 1-factorable?

A
28
Q

2-Factor Facts

A
29
Q

Regular graph of positive even degree has…

A
30
Q

Which Complete Graphs are 2-Factorable?

A
31
Q

Vizing’s Theorem

A
32
Q

Bipartite Graphs and Delta(G) regular graphs

A
33
Q

Bipartite Graph Edge Chromatic Number

A
34
Q

Edge Chromatic Number of Complete Graph

A
35
Q

Jordan Curve Theorem

A
36
Q

Boundary Edge Condition

A
37
Q

Handshaking Lemma for Planar Graphs

A
38
Q

Euler’s Formula for Planar Graphs

A
39
Q

2-connected Planar Graph

A
40
Q

Planar Graph Edge Bound

A
41
Q

Connected Planar Graph Degree Condition

A
42
Q

Kuratowski’s Theorem

A
43
Q

Four Colour Theorem

A
44
Q

Chromatic Number Bound

A
45
Q

Brooke’s Theorem

A
46
Q

Chromatic Polynomial of Connected Components

A
47
Q

Deletion/Contraction Lemma

A
48
Q

Chromatic Polynomial Characteristics

A
49
Q

Chromatic Polynomial of Tree

A
50
Q

Chromatic Polynomial of Cyclic Graph

A