Review For Final Examination (Spring 2011)

Geometric Structures

1. Draw a diagram of the following (when possible the diagram should be drawn in the plane):

a. A right isosceles triangle

b. An equiangular triangle

c. An equiangular 4-gon that is not a square

d. An equilateral quadrilateral that is not a square

e. A non-convex, non-self-intersecting 4-gon

f. A trapezoid with three equal sides that is not a rectangle

g. An equiangular hexagon which is not a regular hexagon

h. A self-intersecting regular octagon

i. A scalene right triangle

j. An obtuse angle triangle

k. A parallelogram which is not a rectangle or a rhombus

l. A rhombus which is not a square

m. A quadrilateral with exactly two, nonadjacent right angles

n. Draw a graph with 9 vertices and 15 edges

o. Draw a 4-valent plane graph with two pentagons, 10 triangles.

p. Draw an isosceles triangle which is not equilateral

q. A non-convex self-intersecting 8 sided polygon

r. A convex plane quadrilateral which corresponds to the side length partition {1, 1, 1, 1 } and angle measure partition {2, 1, 1}.

s. A convex plane quadrilateral which corresponds to the side length partition {2, 1, 1 } and angle measure partition {2, 1, 1}.

t. What is the difference between a ray and a segment?

u. Draw graph which is planar but not plane.

v. Draw a graph which is non-planar. (There is no plane drawing of the graph.)

w. A self-intersecting regular pentagon.

x. A plane graph all of whose faces are triangles and all of whose vertices have the same valence with more than 4 vertices.

2. Give a precise statement of the graph theory version of Euler's formula, and be able to give a proof of this theorem. Draw a plane tree and verify that Euler's formula holds for the tree you draw.

3. Draw two graphs to which one can not apply Euler's formula, each for a different reason.

4. a. Write the p_i values for the faces of the graph H below.

b. Is there a pair of vertices u and v in the graph above such that there are three independent paths between these vertices?

c. Is the graph above 3-connected?

d. Write the v_i values for the vertices of the graph above.

e. Color the vertices of the graph above with as few colors as possible.

f. Color the faces of the graph above with as few colors as possible.

g. Find the distance between vertices 3 and 6 in the graph above.

h. List the cut vertices of H.

i. Draw H - vertex 8; Draw H - vertex 4.

j. Draw the graph H with the edge joining vertices 1 and 4 removed.

5. a. Draw an example of a 3-valent (e.g. every vertex is 3-valent) which is 3-polytopal. b. Repeat with 3-valent replaced by 5-valent.

6. Draw an example of a 4-valent graph (e.g. every vertex is 4-valent) which is 3-polytopal.

7. Draw a plane graph with every vertex having valence at least 3 which is not 3-polytopal.

8. Give a statement of the four color theorem (face version).

9. (a) Can one color the faces of the graph in graph below with exactly 3 colors?

(b) What is the vertex chromatic number for the graph below?

(c) How many faces with 8 sides does the graph above have? How many faces with 4 sides?

13. Briefly describe models for: affine geometry, projective geometry, and hyperbolic geometry in each of the finite and infinite situations.

14. The situations below concern the relation between the Euclidean and real-projective planes.

a. What projective points correspond (if any) to the Euclidean points: (-2, -4); (0, 3); (9, 0)?

b. What Euclidean points correspond (if any) to the real projective points:

(-1, -2, 4); (0, 2, 1); (0, -5, 0); (2, -5, 4); (-2, 0, 0).

c. Find the line that goes through (0, 3, 0) and (-2, 4, 2) in the real projective plane?

d. Find the line through goes through (-2, 4) and (2, 6) in the Euclidean plane.

e. Find the point if there is one where the lines 2x - 3y + 2 = 0 meets -x + 2y + 8 = 0 in the Euclidean plane.

f. Find the point where 2x - y + z = 0 and -x - y + 4z = 0 meet in the real projective plane.

g. Draw a diagram to illustrate Desargues Theorem in the real projective plane.

h. Write down the equation of a line through (0, 2, 0) which passes through the point (-1, 2, 3).

i. Draw a diagram of the Fano plane.

j. If a finite affine plane is coordinatized with numbers from GF(5):

i. How many points will the geometry have? ii. How many lines will the geometry have? iii. How many points will be on every line? iv. How many lines will pass through every point? v. Write down the line that goes through (3, 1) (remember these numbers are from GF(5)). vi. Write down all of the points on 2x -3y = 4 vii. List all of the points on the projective extension to 2x-3y = 4. Remember in GF(5) we can replace -2 say by +3.

15. (a) Draw a taxicab circle centered at (-5, 2) and radius 4.

(c) Determine the set of points which are equidistant from from (-10,2) and (6, 4) in the taxicab plane. (Describe the points using one or more equations.)

16. How many edges are needed for the optimal eulerization of the graph in Problem 4? (Be able to find an Eulerian circuit in a graph and know the characterization theorem for Eulerian circuits.)

17. a. Draw a plane simple polygon which requires three guards.

b. Triangulate the polygon below in two different ways.

c. How many guards does three coloring the vertices of the two triangulations you found give rise to?

d. What is the the minimum number of guards for this polygon?

e. Can you draw a plane simple polygon where the number of guards is smaller than the number of vertex guards? (Thus, putting a guard somewhere other than at a vertex reduces the number of guards needed for that particular polygon.)

f. List the ears of the polygon above.

g. What is the face coloring number of the two triangulations you find for the polygon above?

h. Draw a polygon with exactly 6 ears.

i. Draw a polygon whose interior angles are all either 90 or 270 degrees and which has exactly 12 vertices. Can you find such a polygon where all the side lengths are equal?

j. How many guards do you need for the polygon you drew in i.?

k. Does one need more, the same, or fewer guards for a polygon with n sides where all the interior angles are 90 or 270 degrees compared with an arbitrary n-gon?

18. Compute the portion of the multiplication and addition tables for the integers mod 11, that involve, 2, 5, 7. (For example: 2 x 7 is congruent to 3 mod 11.)

19. (Solve these problems in the projective plane whose points have coordinates in the field of integers mod 5.)

a. List all the points on the line 2x + 3y + z = 0.

b. Find the equation of the line through: (1, 2, 3) and (2, 3, 0).

c. Are (1, 2, 1), (2, 4, 3) and (2, 1, 2) vertices of a triangle?

d. Are the lines 2x + y - z = 0, x + y + z = 0 and 3x + y + z = 0 concurrent?

e. Which points correspond to (2, 3, 4) and (2, 4 2) in the affine plane associated with this projective plane? In that affine plane, find the line through (2, 3) which is parallel to the line x + y + 2 = 0.

e. Find where the lines 2x + y + 3z = 0 intersects x + 2y + 4y = 0

20. Give a precise statement of Desargues Theorem and its dual for the real projective plane.

21. Find the Hamming distance between the strings shown:

a. 111222 and 311222

b. 100011110 and 101111110

c. aaaabbbbcc and ababababcc

22. What are the points and lines in the Cayley-Klein model of the hyperbolic plane?

23. What are the properties of the sum of the angles of a triangle in the Euclidean, projective, and Bolyai-Lobachevsky planes?

23. Show that every triangle tiles the Euclidean plane.

24. What is meant by a zero-divisor? Give an example of an algebraic structure which has zero-divisors.