Graph Theory Problem Bank

Graph Theory Problem Bank
1 Question 1 [Linh Dang]
Consider the relation A of two vertices of a graph G dened by the following:
uAv , u = v or there exist two edge-disjoint paths connecting u and v
Also consider the relation B on the edges of a graph, dened by the following:
e1Be2 , e1 = e2 or e1 and e2 lie on a common cycle
(a) Show that the three prongs required for an equivalence relation apply
to A, then do the same for B.
(b) Recall the denition of a block as either a bridge or a maximal 2-
connected subgraph, and that a graph may be partitioned into blocks. Prove
that a block may be equivalently dened as an equivalence class on B.
2 Question 2 [Andrew Jofre]
In the below, assume G to be a non-trivial graph.
(a) Consider the statement P3, dened as
Graph G has no cut-vertices.
Does P1 provide a necessary or sucient condition for a non-trivial graph
G to be Hamiltonian? Or both, or neither? Justify rigorously.
1
(b) Consider the statement P2, dened as
Graph G is Hamiltonian.
Does P2 provide a necessary or sucient condition for G to be Eulerian?
Or both, or neither? Justify rigorously.
3 Question 3 [Lindsey Pautz]
Prove that, if G is a connected graph of order n 3 with the property that
d(x) + d(y) k
for some 3 k < n and every distinct pair of non-adjacent vertices x; y, then
G contains a path of length k and a cycle of length at least dk=2 + 1e.
4 Question 4 [Yuzhe Ni]
Show that if G is k-connected, for k 2, then every set of k vertices is
contained in a cycle.
5 Question 5 [Brittany Robinson]
Let G be a connected graph such that (G) = k and E0 E(G) is a set of
k edges. How many components can G E0 have?
6 Question 6 [Joseph Pepe]
Let G be a graph such that jGj = n. If the mean of the degrees of the
vertices of G is d, then prove that G contains an induced subgraph H such
that jHj > n=2 and (H) < d.
2
7 Question 7 [Xuchang Yi]
Consider a
ow network (G; f; c; s; t) with the following specications:
V (G) := f(x; y) : x; y 2 [10; 10] \ Zg
arcs between every two vertices with (Euclidean) distance exactly one
c(e) := maxf0; y2 xg, where x and y signify the values of x and y at
the end of the arc and resolves to + for an arc between two ordered
pairs with the same y-coordinate and for an arc between two ordered
pairs with the same x-coordinate.
s is the origin
t is (1; 1)
Draw a picture showing the
ow you obtain after applying the augmenting
path algorithm, as well as the corresponding cut.
8 Question 8 [Cleo You]
Let m denote the size and n the order of a certain graph G.
(a) Prove that
(G) d2m=ne
(b) Prove that this bound is sharp, and that any bipartite graph for which
equality holds either has a perfect matching or has as many components as
it has vertices.
9 Question 9 [Chijun Sha]
Let G = (L;R) be bipartite and let A be the set of vertices with maximal
degree. Show that a complete matching exists between A \ V1 and V2.
3
10 Question 10
Prove [substitute here any theorem whatsoever proven in lecture, homework,
or readings].
11 Question 11
Prove t
4