Exercises

New exercises. We have a few exercises for you.

Remember that a graph is a bunch of points (called vertices) with some pairs connected by segments (called edges). Recall that a k-coloring of a graph is a coloring of the vertices, using k colors. A coloring is called proper if no two neighbors have the same color (in these exercises, we only consider proper coloring). Here is an example of a 3-colored graph:

Another term: if we can draw the graph in the plane so that no two edges cross, we say that the graph is planar.

Now for the exercises. showed that every planar graph must have at least one vertex of degree at most 5, that is, a vertex that is only connected to 5 other vertices or less. Use this below. We alway draw our graphs in the plane, and if the graph is not planar the edges will sometimes cross each other. These intersections are not considered vertices.

Can you construct a planar graph that has no vertex of degree four or less?
Show that every planar graph can be colored using 6 colors. We discussed this last week.
Show that every planar graph can be colored using 5 colors. This is a little trickier.
Warning: This one is hard. Is there a graph that requires 4 colors, that is, cannot be colored using 3 colors? If so, try to find an example as small as possible.
Competition! We said that it appears to be very hard to decide if a given graph admits a proper 3-coloring. As a challenge, prepare a graph with at most 15 vertices. We will distribute these next week and have the students try to decide if the graphs can be 3-colored or not. As a warm-up, check the two graphs below (thank you Kyle!). One is 3-colorable, and the other is not. Can you figure out which is which?

The first graph

The second graph

Older exercises. For the next exercises you will need to use sage for that, but you don't need to install it locally (installing locally is a pretty good idea and is free). If you do not install it, use a sagecell.

To build an an elliptic curve over F_p with defining equation y^2 = x^3 + ax + b:

p = [your prime]
a = [your choice]
b = [your choice]
F = GF(p)
E = EllipticCurve(GF(p),[a,b])

Here are some exercises about elliptic curves:

In this exercise you are asked to calculate DLog in a few of curves. The second is Curve25519 (with the base point above), and that is not an easy thing to do!

Page updated

Google Sites

Report abuse