**Practice 3: Graph Theory
**

Prepared by:

Joseph Malkevitch

Department of Mathematics and Computer Studies

York College (CUNY)

Jamaica, New York

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/

1. For each graph G below find G - v for every vertex of G and G - e for each edge e of G. For each vertex and edge of G state whether or not the vertex/edge is a cut vertex/bridge. (When an edge is removed its endpoints remain in place. If vertex v is removed, v the edges attached to v are removed, but the other end vertex of the edge at v stays in place.) The removal of a cut vertex or bridge (cut edge) increases the number of components of a graph.

a.

b.

c.

2.

a. For each graph above, find the distance between vertex 0 and every other vertex of the graph.

b. For each graph above, find the distance between vertex 4 and all higher numbered vertices.

3. Definition: The *vertex coloring number* of a graph G is the minimum number of labels (colors) that can be assigned to the vertices of G so that two vertices joined by an edge get different labels.

The vertex coloring number of a graph is usually denoted by the Greek letter chi.

Find the vertex coloring number for all of the graphs drawn above.

4. Definition: If G is a connected graph, and v is any vertex of G, the *eccentricity* of v, denoted e(v) is the farthest distance that any vertex w of G can be from v. (e(v) is a non-negative integer.)

Find the eccentricity of each vertex in the tree below: