Graph Theory Practice

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/


Graphs are a fascinating tool for problem solving and for geometric explorations. I will use the graph concept as an organizing idea to consider a broad array of topics in geometry: polyhedra, polygons, tilings, lattice point problems, symmetry, and models for different types of finite geometries.

When there are no explicit restrictions on how to draw your graph(s), where possible draw the graph diagrams without loops and multiple edges and as connected plane graphs.

The degree or valence of a vertex v in a graph (without loops) is the number of edges at v. If there are loops at v each loop contributes 2 to the valence of v. One can think of the the valence of v as the "local" number of lines that meet at v.

A graph is connected if for any pair of vertices u and v one can get from u to v by moving along the edges of the graph. Such routes that move along edges are known by different names: edge progressions, paths, simple paths, walks, trails, circuits, cycles, etc. The usual difference between the terms is whether the routes repeat vertices other than the start vertex, repeat edges, etc.

A graph is called plane if it can be drawn in the plane so that edges meet only at vertices. Some drawings of graphs in the plane have edges that meet at points other than vertices but these "accidental crossings" can be eliminated using a different drawing. A graph which has the potential to be drawn as a plane graph is known as a planar graph. One talks about the embedding of a graph in the plane and some graphs have embeddings where edges meet only at the vertices.

0.

a. Write down the valences of the 16 vertices in the graph below:

b. Draw another graph which is not isomorphic to this one which is plane and has 16 vertices.

1. Is there a connected graph whose valences are:

a. 5, 3, 2, 2, 2, 1, 1

b. 8, 6

c. 5, 5, 3, 3, 3, 2, 2, 2, 2, 2

d. 5, 3, 3, 3, 2, 2, 2, 2, 2

e. 4, 4, 4, 4, 4, 4, 4, 4, 4

2. Draw as many connected graphs whose vertices have valences:

5, 3, 2, 2, 2, 1, 1

as you can and which have no loops or multiple edges and are non-isomorphic.

3. Can you find a connected graph whose degrees are without loops or multiple edges:

4, 4, 4, 4, 4

Can you draw this graph in the plane so that edges meet only at vertices?

4. For the graph below:

a. A snow plow starts at vertex 0 and must return to vertex 0 using a route which visits each edge at least once and repeats a minimum number of edges. Find such a route and how many repeated edges does it have?

Assume that the edges all have the length, say length 1.

b. Repeat doing question a. under the assumption that vertical edges have length 1, horizontal edges have length 5, and the "diagonal edges" have length 3.

5. For the graph below:

a. What is the shortest route from 0 to 3? What is the shortest route from 0 to 8? (Route length is the sum of the weights of the edges in the route. When no weight is assigned to an edge the weight is assumed to be 1.)

b. What is the shortest route from 5 to 2? What is the shortest route from 5 to 5 to 2?

c. What is the shortest route from 7 to 2? From 7 to 0?