Problem 1
Let G be the graph of the tic-tac-toe board: 12 vertices, 12 edges, it looks like a #.
(a) How many vertices of G have degree equal to 1?
(b) Find an edge of G so that if you delete that edge, the remaining graph is a tree.
(c) How many faces does G have? Verify Euler's formula for G.
(d) What is the minimum number of edges you need to add to G so that the new graph has an Eulerian circuit? (You do not get to add any more vertices.)
Problem 2
Let G be the graph K_5 with a single edge removed. Draw a planar representation of G, and verify Euler's formula for G.
Problem 3
Explain in your own words why there are exactly 5 solutions to the equation 1/p+1/q=1/2+1/E, where p,q, and E are positive integers, all at least three.
Problem 4
Show that it is impossible to construct a polyhedron whose faces are all hexagons.
Problem 5
Show that it is impossible to have a graph which has 5 vertices of degree 3, 2 vertices of degree 4, and 1 vertex of degree 6.
Problem 1
Suppose that a certain planar graph G has 13 faces:12 triangles and 1 square. Find the number of edges in G. Then use Euler's formula to find the number of vertices in G.
Problem 2
Which of the complete bipartite graphs K_{n,m} have an Eulerian circuit?
Problem 3
Show that if a tree has 5 vertices, the sum of the vertex degrees must be 8. Then give an example of a tree with 5 vertices whose vertex degrees are 3,2,1,1,1.
Problem 4
Give the planar representation of the octahedron, and verify Euler's formula.
Problem 5
Explain, in your own words, the argument using Euler's formula which proved that K_{3,3} was not planar.
Note: I could not draw the graphs in html, you'll have to provide you own examples!
Problem 1
Let G be the graph pictured below.
(a) Find the degree of vertex B, and find the degree of the face ABCDE.
(b) Either find an Eulerian circuit in G or explain why such a circuit cannot exist.
Problem 2
Suppose that a graph G has 3 connected components, each of which is a tree.
(a) If G has 14 vertices, how many edges does G have? Be sure to explain why your answer applies to all such graphs, not only a particular graph.
(b) Does Euler's formula holds for G? Why or why not?
Problem 3
Draw a planar representation of the complete bipartite graph K_{2,4}. How many faces does your planar graph have? Does Euler's formula hold?
Problem 4
Prove that the graph below is not planar.
Problem 5
A soccer ball is a polyhedron consisting of 20 hexagons and 12 pentagons. There are 60 vertices, each of degree 3. How many edges does the soccer ball have?
Problem 6
Prove that any polyhedron whose faces are only pentagons and hexagons must have at least 12 pentagons. (Possible hint: Use 2E>= 3V, Euler's formula, and the face degrees.)