Exam Revision

Question 1

Planar graph

Answer 1

a graph that can be drawn in the plane in such a way that no edges cross each other, and no edge touches a vertex other than its endpoints

Question 2

Relationship between n (vertices), m (edges) and r (regions) in planar graph

Answer 2

n - m + r = 2

Question 3

Bipartite graph

Answer 3

a graph G = (V, E) with the property that V can be partitioned into two disjoint sets V1 and V2 such that V = V1 ∪ V2 and every edge has one endpoint in V1 and the other in V2.

Question 4

Bipartite graph definition using colouring

Answer 4

A graph that has a proper colouring using two colours

Question 5

Bipartite graph definition using cycles

Answer 5

A graph that does not contain any cycles of odd length

Question 6

R(4,5)=R(5,4)=

Answer 6

25

Question 7

Subgraph

Answer 7

A subgraph of a graph G is a graph obtained from G by deleting vertices and/or edges

Question 8

Bipartite graph

Answer 8

a graph that does not contain any cycles of odd length

Question 9

Hamiltonian cycle

Answer 9

a Hamilton cycle in a graph G is a cycle in the graph which contains every vertex (exactly once)

Question 10

Proper k-colouring

Answer 10

A proper k-colouring of a graph G is a function f : V (G) → {1, . . . , k} such that f(u) =/= f(v) whenever uv ∈ E(G).

Question 11

Clique number

Answer 11

The clique number of a graph G is the largest natural number t such that G contains Kt as a subgraph

Question 12

Independent set

Answer 12

An independent set in a graph G is a set U ⊆ V (G) such that no edge in G has both endpoints in U.

Question 13

Independence number

Answer 13

The independence number of G is the size of the largest independent set in G.

Question 14

Ramsey number R(s, t) for integers s, t > 2. 4

Answer 14

The Ramsey number R(s, t) (for natural numbers s and t) is the smallest natural number n such that every colouring of the edges of Kn with red and blue contains either a copy of Ks with all edges red or a copy of Kt with all edges blue.

Question 15

Using the fact that R(4, 4) = 18, show that the graph in part 2(ii)b must contain an independent set of size at least 4.

Answer 15

Since R(4, 4) = 18, any graph with 18 vertices must contain either a clique or independent set on 4 vertices. The graph in part (ii)(b) has 18 vertices and does not contain any clique on 4 vertices (since the clique number is 3), so it must contain an independent set of size at least 4.

Question 16

Connected graph

Answer 16

A graph G is connected if, for every two distinct vertices u, v ∈ V (G), there is a path from u to v

Question 17

Spanning tree

Answer 17

A spanning tree for a connected graph G is a spanning subgraph of G that is a tree.

Question 18

Connected component

Answer 18

A connected component of G is a maximal connected induced subgraph of G

Question 19

Brute force algorithm

Answer 19

enumerates every possible solution and tests each one

Question 20

greedy algorithm

Answer 20

focuses on making the best short term decision without considering long term consequences

Question 21

P-problem

Answer 21

can be solved by an algorithm within a time bounded by a polynomial function of the problem size

Question 22

NP- problem

Answer 22

a potential solution can be checked in polynomial time

Question 23

Eulerian graph

Answer 23

contains a closed walk that includes every edge exactly once

Question 24

Hamiltonian graph

Answer 24

contains a cycle that includes every vertex once

Question 25

what two conditions must a flow satisfy to be valid?

Answer 25

1. For every edge the flow across that edge must be less than or equal to its capacity
2. For every vertex other than the source and the sink, the sum of the flow over the in-edges equals the sum of the flows over the out-edges

Question 26

Planar graph inequality

Answer 26

m less than or equal to 3n-6

Question 27

Kn has how many edges?

Answer 27

1/2*n(n-1)

Question 28

Strong induction vs standard induction

Answer 28

In a proof by strong induction, the inductive hypothesis says that the result is true for all natural numbers between the base case, up to a natural number k. In standard induction, the inductive hypothesis says that the result is true for some natural number k (without assuming it’s true for any values less than k).

Question 29

Independent set

Answer 29

a set U ⊆ V (G) with the property that no
edge in G has both incident vertices in U

Question 30

Hall’s Marriage Theorem

Answer 30

t a bipartite graph with bipartition
(U, W), where |U| = |W|, contains a perfect matching if and only for all U’ ⊆ U,
we have | NG(U’)|>| U’|.

Question 31

Augmenting path

Answer 31

An augmenting path in a basic flow network, with respect to a given flow, is an undirected path from the source to the sink such that no forward edge on the path is saturated, and every backward edge has non-zero flow

Question 32

Euler’s formula

Answer 32

n - m + r = 2 where n is the number of vertices, m is the number of edges, and r is the number of regions in the planar drawing

Question 33

Simple graph

Answer 33

the adjacency matrix must be symmetric about the main diagonal and have no loops

Question 34

Ramsey’s Theorem

Answer 34

For all s, t ⩾ 2, there is a natural number n such that every colouring of the edges of Kn with red and blue contains either a copy of Ks with all edges red or a copy of Kt with all edges blue

Question 35

Let G be a connected planar graph with n ≥ 3 vertices and m edges. Then

Answer 35

m ≤ 3n − 6.