Graph Theory

Question 1

What is a graph?

Answer 1

Pair of sets (V(G),E(G)), where each element of E consists of a pair of elements of V

Question 2

What is a walk in a graph G?

Answer 2

A sequence of vertices v_1 v_2 … v_n such that {v_i, v_i+1} is in E(G) for 1 <= i < n

Question 3

What is a path in a graph G?

Answer 3

A walk where all the vertices are distinct

Question 4

What is a cycle?

Answer 4

A closed walk of at least 3 vertices with otherwise distinct vertices

Question 5

What does is mean for a graph G to be connected?

Answer 5

For any two vertices x,y in V(G), there is an xy-walk in G

Question 6

What does it mean for two vertices x,y to lie in the same component?

Answer 6

They are joined by an xy-walk

Question 7

What is a tree?

Answer 7

A minimally connected graph

Question 8

Prove that any tree is acyclic

Answer 8

• SFAC there is a cycle in T
• Remove some edge e in this cycle
• Then we obtain a path, P
• Take two vertices x,y in T
• Since T is connected, there is an xy-walk between them
• If this walk used the edge we removed, replace it with the path P
• This is still an xy-walk
• So T-{e} is connected
• Contradicts minimality of T
• So T is acyclic

Question 9

Prove that a connected & acyclic graph G is a tree

Answer 9

• SFAC G - {e} is connected for some e = xy in G
• Let W be a shortest xy-walk in G-{e}
• Then W must be an xy-path (otherwise it wouldn’t be the shortest)
• So if we add e back in, we get a cycle, but G was acyclic, contradiction

Question 10

Prove that any two vertices in a tree are joined by a unique path

Answer 10

• SFAC this isn’t true
• i.e. there are two distinct xy-paths in T, P_1 and P_2
• Suppose P_1 is the shortest over all such choices of x and y
• Then P_1 and P_2 intersect only at x and y
• But this is a cycle, contradiction

Question 11

Prove that any tree with at least two vertices has at least two leaves

Answer 11

• Let P be a longest path in T
• If the start / end of P had another neighbour in V(T)/V(P), we could make the path longer
• If the start / end of P had another neighbour in V(P) other than the next in the sequence P, we would have a cycle
• So the two ends of P must be leaves.

Question 12

What is a leaf?

Answer 12

A vertex of degree 1

Question 13

Prove that if T is a tree and v is a leaf, then T-v is a tree

Answer 13

• Suffices to show T-v is connected & acyclic
• Know T is acyclic, and we can’t create a cycle by removing an edge, so T-v is acyclic
• Know T is connected
• For any x,y in T-v, the unique xy-path in T is contained in T-v
• So T-v is a tree

Question 14

Prove that any tree on n vertices has n-1 edges

Answer 14

• By induction
• A tree with 1 vertex has 0 edges
• Consider a tree T on n vertices
• Know T has a leaf v
• Know T-v is a tree
• T-v has n-1 vertices and n-2 edges by induction hypothesis
• So T has n vertices & n-1 edges

Question 15

What is a spanning tree?

Answer 15

Minimally connected subgraph of the same vertex set

Question 16

Prove that a connected graph with n-1 edges and n vertices is a tree

Answer 16

• Let H be a spanning tree of G
• H has n vertices and n-1 edges
• so H=G, i.e. G is a tree

Question 17

What is a minimum cost spanning tree of G?

Answer 17

A spanning tree T of G such that for any other spanning tree T’, C(T’) >= C(T)

Question 18

Describe Kruskal’s algorithm

Answer 18

• A_0 = {}
• Check if there is an edge e in G / A_i such that (V(G), A_i U {e}) is acyclic
• If not, output A = A_i and stop
• If there is, set A_i+1 = A_i ∪ {e} for one such e such that c(e) is minimal, then increase i by 1

Question 19

Prove that Kruskal’s algorithm produces a minimum cost spanning tree of G

Answer 19

[CONTINUE]

Question 20

What is an Euler trail?

Answer 20

A walk such that every edge in a graph appears exactly once

Question 21

What is an Euler tour?

Answer 21

A closed Euler trail

Question 22

What is an Eulerian graph?

Answer 22

A graph where every edge is of even degree (in an Euler tour, we use one edge to enter a vertex, and a different edge to leave).

Question 23

What is Eulers theorem?

Answer 23

a connected Eulerian graph has an Euler Tour

Question 24

Prove Eulers theorem

Answer 24

• Will prove that Fleury’s algorithm produces an Euler tour.
• [CONTINUE]

Question 25

Describe Fleury’s Algorithm

Answer 25

• Start at any vertex
• Follow a walk, deleting each edge after it is used
• At each step, ensure that after any isolated vertices are removed the graph is still connected, and that we do not run along an edge to a leaf, unless that is the only option.

Question 26

Prove that in any graph there are an even number of vertices of odd degree

Answer 26

• The sum of the degrees of all the vertices in a graph is equal to 2 x no. of edges (since each edge connects to two vertices).
• So the sum of the degrees of the vertices must be even
• So there must be an even number of odd degree vertices

Question 27

What is a Hamiltonian cycle?

Answer 27

A closed walk that visits every vertex exactly once

Question 28

What is a hamiltonian graph?

Answer 28

A graph that contains a Hamiltonian cycle

Question 29

State Ore’s theorem

Answer 29

• G a connected graph with n >= 3 vertices
• For every pair of non-adjacent vertices x & y, d(x) + d(y) >= n
• Then G is hamiltonian

Question 30

State Dirac’s theorem

Answer 30

• G connected graph with n>= 3 vertices
• For ever vertex v, d(v) >= n/2
• Then G is Hamiltonian

Question 31

Prove that if G is connected an non-hamiltonian, then the length of the longest path is at least as long as the longest cycle

Answer 31

• Let C be a longest cycle with length L
• Since G is not hamiltonian, there is some vertex not in C.
• Since G is connected, there is some edge vu with u in C and v not in C
• Remove an edge of C that contains u and replace it with uv
• This gives a path of length L

Question 32

Prove ore’s theorem

Answer 32

• SFAC G is not hamiltonian
• Let P = x1 x2 … xk be a longest path in G
• P has length k-1
• So G doesn’t have a cycle of length k (length of longest path >= length of longest cycle)
• So x1 and xk are not adjacent
• So d(x1) + d(xk) >= n
• [CONTINUE]

Question 33

What is an L-shortest xy-path?

Answer 33

An xy-path P that minimises L(P)

Question 34

Describe Dijkstra’s algorithm

Answer 34

• Goal: Find an L-shortest xy-path
• Set U = V(G), D(x) = 0, D(v) = infinity for v != x
• If U is empty, stop
• Otherwise:
  
  • Pick u in U with D(u) minimal
  • Delete u from U
  • For any v in U that is adjacent to u, with D(v) > D(u) + L(uv), replace D(v) by D(u) + L(uv)
• Repeat

Question 35

What is an L-shortest paths tree rooted at x of a graph G?

Answer 35

• A spanning tree T
• For any y in V(G), the unique xy path in T is an L-shortest xy-path in G.

Question 36

Wrt Dijkstra’s, what is the parent of a vertex v?

Answer 36

The last vertex u such that we replaced D(v) by D(u) + L(uv)

Question 37

How would you use Dijkstra’s to get an L-shortest paths tree rooted at x?

Answer 37

• Run the algorithm
• Determine the parent of each vertex
• Draw an edge from each vertex to its parent

Question 38

What is a matching?

Answer 38

A subset of the edge set M such that the edges in M are pairwise disjoint.

Question 39

What is a perfect matching?

Answer 39

A matching M such that every vertex of the graph belongs to some edge of M

Question 40

What is a bipartite graph G?

Answer 40

A graph such that V(G) can be partitioned into two sets A, B so that every edge of G crosses between A and B

Question 41

If M is a matching and P is a path, what does it mean for P to be an M-alternating path?

Answer 41

Every other edge of P is in M

Question 42

If M is a matching and P is a path, what does it mean for P to be an M-augmenting path?

Answer 42

Every other edge of P is in M and it’s end vertices are not in any edge of M

Question 43

If M is a matching in G, prove that M is not of maximum size if and only if there is an M-augmenting path in G

Answer 43

• If there is an M-augmenting path in P, we can create a larger matching by “flipping” every edge of P (replace M by M \ (M ∩ E(P)) ∪ (E(P) \ M))
• Suppose M* is a matching with more edges than M
• Let H = M U M*
• Every vertex has degree at most 2 in H
• So each component of H is an edge, path or cycle
• The edge components consist of M ∩ M*
• The edges in path and cycle components alternate between M and M*
• As |M| > |M| we can find a path component with more edges of M
  than M
• This is an M-augmenting path in G.

Question 44

Describe the Hungarian algorithm for finding a maximum matching in G

Question 45

What is a cover of G?

Answer 45

A set of vertices C such that every edge contains at least one vertex of C

Question 46

What is the relationship between the size of a matching and the size of a cover?

Answer 46

|M| <= |C|

Question 47

What is Konig’s theorem?

Answer 47

In any bipartite graph, the size of a maximum matching equals the size of a minimum cover

Question 48

Prove Konig’s theorem

Question 49

For a bipartite graph with parts A,B and a set S, a subset of A, what is the neighbourhood of S?

Answer 49

N(S) = ∪a∈S{b : ab ∈ E(G)}

i.e. the set of vertices in B that are joined by an edge to a vertex in S

Question 50

What is Hall’s theorem?

Answer 50

• Let G be a bipartite graph with parts A,B
• Then G has a matching covering A if and only if every S a subset of A has |N(S)| >= |S|

Question 51

Prove Hall’s theorem

Question 52

What is a postman walk in G?

Answer 52

A walk that uses every edge in G at least once

Question 53

Describe Edmond’s algorithm for the chinese postman problem

Question 54

For a graph H in which not all degrees are even, prove there is a path in H such
that both ends have odd degree

Question 55

Prove that Edmonds’ Algorithm finds a minimum length postman walk.

Question 56

What is the chinese postman problem?

Answer 56

The problem of finding the shortest postman walk - a walk that uses every edge of G at least once