Review For Final Examination (Spring 2015)

Geometric Structures

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. 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 (all sides of unequal length) right triangle

j. An obtuse angle triangle which is not scalene

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, and not connected.

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.

y. One of the three regular tilings of the plane.

z. A Euclidean circle of radius 4.

2. Give a precise statement of the graph theory version of Euler's Polyhedral Formula 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 pi values for the faces and the values of vi for the vertices 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 valences 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.

k. List the cut edges (also known as bridges) for H.

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) What is the edge chromatic number of the graph below?

(d) If the Chinese Postman Problem is solved for the graph below, at least how many repeated edges will there have to be?

(e) Draw a plane connected graph with 12 vertices which has no Eulerian circuit.



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

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

11. 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); (-1, -1, -1).

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 (finite filed with 5 elements)):

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.

12. (a) Draw a taxicab circle centered at (-5, 2) and radius 4. (b) Find the taxicab distance between the pairs of points: i. (-2, 3) and (-7, -9); ii. (4, -5) and (-5, 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.) d. Find the points in the taxicab plane which are equidistant from (-4, -4) and (0,0). How does your answer compare with what happens in the Euclidean plane?

13. 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.)

14. 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 vertex 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?

15. 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.)

16. (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 + 4z = 0

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

18. Find the Hamming distance between the strings shown:

a. 311222 and 311123

b. 100011110 and 101111111

c. aaaabbbbcc and ababababcb

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

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

21. Show that every triangle tiles the Euclidean plane.

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


23. Given the graph G below:


a. Draw G - e;

b. Draw G - f

c. Draw G - edge bd

d. Draw G - a

e. Draw G - edge ie

f. List the bridge edges (edges which when removed disconnect the graph) of G

g. List the cut vertices (vertices which when removed disconnected the graph) of G

h. Draw the graph induced by the set of vertices: { a, d, e, i }

i. Draw the graph induced by the set of vertices: {a, b, d, e, i }

j. Does the graph which is a 4-cycle arise as an induced subgraph of G?

k. Find a spanning tree of G

l. Draw the dual of the graph obtained by finding G - f as well as the "isolated" vertices h and g which result.

24. Given the graph H below:



a. Draw the dual of H ; b. If pk denotes the number of faces with k sides in a plane graph, find the pk values for H and its dual; c. Find the minimum number of colors to color i. the vertices ii. the faces of H.

25 Given: Let g(x) = and f(x) = compute:

a. f(-3.2) b. g(-3.2) c. f(3.4) d. g(3.5) e. f(3/4) f. g ( f-2.1) =

Evaluate the following sums:

a.

b. (a is a constant)

26. Evaluate the determinants:

a.



b.



c. Are the points (0, 1, 3), (2, 1, 0) and (0, 3, 1) collinear in the real projective plane?

d. Are the points (0, 1), (1, 4) and (-1, 3) collinear in the Euclidean plane?

e. Find the non-negative number between the modulus -1 which is congruent to the following:

i. 36 mod 5; ii. -23 mod 11; iii. -45 mod 9; iv. 37 mod 12; v. 3x11 mod 6

f. Is there a finite field with 16 elements? Is there a finite field with 12 elements?

g. Is there a finite affine plane with exactly 49 points?

h. Is there a finite projective plane with exactly 31 points?