Graph Theory

Question 1

Define a graph

Answer 1

An ordered pair (V, E), where V is a non-empty finite set and E is an unordered subset of 2 elements of V.

Question 2

Define isomorphic graphs

Answer 2

Two graphs, G and H are isomorphic if there exists a bijection φ: V(G) → V(H) such that xy ∈ E(G) if and only if φ(x)φ(y) ∈ E(H).

Question 3

Define a subgraph

Answer 3

H is a subgraph of G if H is a graph with V(H) ⊆ V(G) and E(H) ⊆ E(G).

Question 4

Define a complete graph

Answer 4

The graph with all possible edges included.

Question 5

Define an empty graph

Answer 5

The graph with vertices and no edges.

Question 6

Define a path graph

Answer 6

The graph with V = {v0, v1, …, vn} and E = {v0v1, v1v2, …, v(n-1)vn}.

Question 7

Define a cycle graph

Answer 7

The graph with V = {v0, v1, …, vn} and E = {v0v1, v1v2, …, v(n-1)vn, vnv0}.

Question 8

Define adjacent vertices

Answer 8

Given a graph G, two vertices, v and w are adjacent if vw ∈ E(G).

Question 9

Define a walk

Answer 9

Given a graph G, a walk is a sequence v0v1…vt of (not necessarily distinct) vertices of G such that v(i-1)vi ∈ E(G) for all 1 ≤ i ≤ t.

Question 10

Define a closed walk

Answer 10

A closed walk is a walk with the same first and last vertices.

Question 11

Define a path

Answer 11

A path is a walk with distinct vertices.

Question 12

Define connected vertices

Answer 12

Vertices x, y in G are connected if there exists a path between them.

Question 13

Define a connected graph

Answer 13

G is connected if every pair of points in G is connected.

Question 14

Define a component of a graph

Answer 14

H is a component of a graph G if it is a connected subgraph of G.

Question 15

Define an acyclic graph

Answer 15

A graph G is acyclic if it does not have any subgraphs which are cycles.

Question 16

Define a tree

Answer 16

A tree is a connected acyclic graph.

Question 17

Define a minimal connected graph

Answer 17

A graph G is minimal connected if it is connected, but removing any edge e from E(G) results in G – e not being connected.

Question 18

Define neighbours

Answer 18

If uv ∈ E(G), then we say that u and v are neighbours.

Question 19

Define a neighbourhood

Answer 19

Given v ∈ V(G), the neighbourhood of v is Γ(v) = {neighbours of v}.

Question 20

Define an incident edge

Answer 20

If e = uv ∈ E(G), then we say e is incident to u and v.

Question 21

Define a degree

Answer 21

The degree of v ∈ V(G) is |Γ(v)|.

Question 22

Define a leaf

Answer 22

A leaf is a vertex with degree 1.

Question 23

Define a spanning subgraph

Answer 23

A spanning subgraph of G is a subgraph H such that V(G) = V(H).

Question 24

Define a spanning tree

Answer 24

A spanning subgraph which is also a tree.

Question 25

Define a weighted graph

Answer 25

A graph with a positive weight assigned to each edge.

Question 26

Define the cost of a set of edges

Answer 26

The cost of S ⊆ E(G) is the sum of the cost of all the edges in S.

Question 27

Define a minimal cost spanning tree

Answer 27

S ⊆ E(G) such that (V(G), S) is a connected subgraph of G and the cost of S is minimised.

Question 28

Give Kruskal's Algorithm

Answer 28

Begin with A0 = ∅. At step i ≥ 0, if there is an edge e ∈ E(G)\Ai such that (V(G), Ai + e) is acyclic, set A(i+1) = Ai + e and proceed to step i + 1, otherwise stop.

Question 29

Define an Euler trail

Answer 29

An Euler trail in a graph G is a walk in G where every edge of G appears exactly once.

Question 30

Define an Euler tour

Answer 30

An Euler tour is an Euler trail which begins and ends at the same vertex.

Question 31

Define an Eulerian graph

Answer 31

A graph which has an Euler tour.

Question 32

Define an isolated vertex

Answer 32

A vertex of G is isolated if the degree of the vertex is 0.

Question 33

State the handshaking lemma

Answer 33

In any graph, there are an even number of vertices with odd degree.

Question 34

State Fleury's algorithm

Answer 34

Start at any vertex v0 of G and initially let H = G. At every step, if vi is isolated, stop. Otherwise, pick any neighbour v(i+1) of vi such that once removing viv(i+1) and any isolated points from H, H will still be connected. Then, repeat.

Question 35

Define a Hamiltonian cycle

Answer 35

A cycle in G which contains every vertex of G.

Question 36

Define a Hamiltonian graph

Answer 36

A graph which contains a Hamiltonian cycle.

Question 37

State Ore's Theorem

Answer 37

Let G be a graph with n ≥ 3 edges. Suppose that for every pair of non-adjacent vertices x and y, d(x) + d(y) ≥ n, then G is Hamiltonian.

Question 38

Define the l-length of a path

Answer 38

Given a connected graph G with an assigned length l(e) for each e ∈ E(G), the l-length of a path P is the sum of all l(e) for edges e ∈ P.

Question 39

Define the l-shortest path

Answer 39

Given two vertices x, y ∈ V(G), the l-shortest path is an xy-path P that minimises l(P).

Question 40

State Dijkstra's algorithm

Answer 40

Begin with U = V(G)\{x} and let D(v) = ∞ for all v ∈ V(G)\{x}. The algorithm will terminate whenever U is empty. At each step of the algorithm, pick u ∈ U such that D(u) is minimal and for any v ∈ U adjacent to u, let (D(v) = min(D(v), D(uv)).

Question 41

Define a parent vertex

Answer 41

For any vertex, the parent of v is the last vertex to be assigned a finalised value.

Question 42

Define a bipartite graph

Answer 42

A graph G is bipartite if we can partition V(G) into two sets A and B such that every edge crosses between A and B.

Question 43

Define a matching

Answer 43

M ⊆ E(G) is a matching if the edges in M are pairwise disjoint.

Question 44

Define a perfect matching

Answer 44

A matching M is perfect if every vertex belongs to some edge of M

Question 45

Define an alternating path

Answer 45

Given a graph G, a matching M and a path P, P is M-alternating if every other edge of P is in M.

Question 46

Define an augmented path

Answer 46

Given a graph G, a matching M and a path P, P is M-augmenting if P is M-alternating and its end vertices are not in any edge of M.

Question 47

State the search algorithm

Answer 47

Start with R = A*, then repeat the following step: if there is an edge directed from some x ∈ R to y ∉ R, then add y to R, otherwise stop. There is a directed path from A* to B* if and only if the final R intersects B*.

Question 48

State the Hungarian algorithm

Answer 48

Start with M = ∅. Orient the edges in G such that all edges in M are one-way from B to A and all the edges not in M are one-way from A to B. Let A* and B* be the vertices that are not in any edge of M. Use the search algorithm to find a directed path from A* to B*. If there is no such path stop, otherwise the path is M-augmenting and we can flip the path to increase the size of M. Then repeat.

Question 49

Define a cover

Answer 49

A cover of a graph G is a subset of vertices C such that every edge contains at least one vertex of C.

Question 50

State Konig's Theorem

Answer 50

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

Question 51

State Hall's Theorem

Answer 51

Let G be a bipartite graph with parts A and B. Then G has a matching covering A if and only if every S ⊆ A satisfies |N(S)| ≥ S.

Question 52

Define a postman's walk

Answer 52

W is a postman walk of G if it is closed and uses every edge of G.

Question 53

State Edmond's Algorithm

Answer 53

Let X be the set of vertices with odd degree in G. For each x ∈ X, find the shortest path tree Tx rooted at x. Find a perfect matching M on X with minimum weight. This works as |X| is even by the handshaking lemma. Let G* be the Eulerian extension of G obtained by copying all edges in the xy-path in Tx for all xy in the matching. Find an Euler tour in G* and then interpret this as a postman walk.