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

Last Updated on February 11, 2019 by EssayPro