Chapter 3: Connectivity and Paths

Question 1

Adjacency Matrix Walk Counting

Answer 1

Question 2

Vertex/Edge Relationship with Connected Components

Answer 2

Question 3

Connected Graph on n vertices has how many edges?

Answer 3

Question 4

Euler’s Theorem (Eulerian Graph)

Answer 4

Question 5

All degrees even means what for maximal trails?

Answer 5

Question 6

Semi-Eulerian Condition

Answer 6

Question 7

Fleury’s Algorithm

Answer 7

Question 8

Hamiltonian Cycle Relationship with connected components

Answer 8

Question 9

Hamiltonian and Bipartite implies

Answer 9

Question 10

Dirac’s Theorem

Answer 10

Question 11

Ore’s Theorem

Answer 11

Question 12

Tree Leaf Facts

Answer 12

Question 13

Edges in a cycle are not…

Answer 13

Question 14

Characterisation of Trees with n vertices

Answer 14

Question 15

Tree/Path Condition

Answer 15

Question 16

Tree More Facts

Answer 16

Question 17

Prüfer Code Facts

Answer 17

Question 18

Cayley’s Theorem, 1889

Answer 18

Question 19

Matching/Augmenting Path Relationship

Answer 19

Question 20

Berge, 1957

Answer 20

Question 21

Hall’s Theorem

Answer 21

Question 22

k-regular, Bipartite implies

Answer 22

Question 23

Corollary 1.12 (Bipartite, Neighbourhood, Cardinality)

Answer 23

Question 24

1-Factor Facts

Answer 24

Question 25

Tutte 1947

Answer 25

Question 26

Bipartite perfect matching decomposition condition

Answer 26

Question 27

Which complete graphs are 1-factorable?

Answer 27

Question 28

2-Factor Facts

Answer 28

Question 29

Regular graph of positive even degree has…

Answer 29

Question 30

Which Complete Graphs are 2-Factorable?

Answer 30

Question 31

Vizing’s Theorem

Answer 31

Question 32

Bipartite Graphs and Delta(G) regular graphs

Answer 32

Question 33

Bipartite Graph Edge Chromatic Number

Answer 33

Question 34

Edge Chromatic Number of Complete Graph

Answer 34

Question 35

Jordan Curve Theorem

Answer 35

Question 36

Boundary Edge Condition

Answer 36

Question 37

Handshaking Lemma for Planar Graphs

Answer 37

Question 38

Euler’s Formula for Planar Graphs

Answer 38

Question 39

2-connected Planar Graph

Answer 39

Question 40

Planar Graph Edge Bound

Answer 40

Question 41

Connected Planar Graph Degree Condition

Answer 41

Question 42

Kuratowski’s Theorem

Answer 42

Question 43

Four Colour Theorem

Answer 43

Question 44

Chromatic Number Bound

Answer 44

Question 45

Brooke’s Theorem

Answer 45

Question 46

Chromatic Polynomial of Connected Components

Answer 46

Question 47

Deletion/Contraction Lemma

Answer 47

Question 48

Chromatic Polynomial Characteristics

Answer 48

Question 49

Chromatic Polynomial of Tree

Answer 49

Question 50

Chromatic Polynomial of Cyclic Graph

Answer 50