Exam Revision Flashcards
Planar graph
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
Relationship between n (vertices), m (edges) and r (regions) in planar graph
n - m + r = 2
Bipartite graph
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.
Bipartite graph definition using colouring
A graph that has a proper colouring using two colours
Bipartite graph definition using cycles
A graph that does not contain any cycles of odd length
R(4,5)=R(5,4)=
25
Subgraph
A subgraph of a graph G is a graph obtained from G by deleting vertices and/or edges
Bipartite graph
a graph that does not contain any cycles of odd length
Hamiltonian cycle
a Hamilton cycle in a graph G is a cycle in the graph which contains every vertex (exactly once)
Proper k-colouring
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).
Clique number
The clique number of a graph G is the largest natural number t such that G contains Kt as a subgraph
Independent set
An independent set in a graph G is a set U ⊆ V (G) such that no edge in G has both endpoints in U.
Independence number
The independence number of G is the size of the largest independent set in G.
Ramsey number R(s, t) for integers s, t > 2. 4
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.
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.
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.
Connected graph
A graph G is connected if, for every two distinct vertices u, v ∈ V (G), there is a path from u to v
Spanning tree
A spanning tree for a connected graph G is a spanning subgraph of G that is a tree.
Connected component
A connected component of G is a maximal connected induced subgraph of G
Brute force algorithm
enumerates every possible solution and tests each one
greedy algorithm
focuses on making the best short term decision without considering long term consequences
P-problem
can be solved by an algorithm within a time bounded by a polynomial function of the problem size
NP- problem
a potential solution can be checked in polynomial time
Eulerian graph
contains a closed walk that includes every edge exactly once
Hamiltonian graph
contains a cycle that includes every vertex once
what two conditions must a flow satisfy to be valid?
- For every edge the flow across that edge must be less than or equal to its capacity
- 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
Planar graph inequality
m less than or equal to 3n-6
Kn has how many edges?
1/2*n(n-1)
Strong induction vs standard induction
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).
Independent set
a set U ⊆ V (G) with the property that no
edge in G has both incident vertices in U
Hall’s Marriage Theorem
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’|.
Augmenting path
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
Euler’s formula
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
Simple graph
the adjacency matrix must be symmetric about the main diagonal and have no loops
Ramsey’s Theorem
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
Let G be a connected planar graph with n ≥ 3 vertices and m edges. Then
m ≤ 3n − 6.
