Vertices, Edges and Degree
Simple and Complete Graphs
Planar Graph and Faces
Euler's Formula
Walks, Trails, Paths
100
What is the name for the number of edges that touch a vertex?
The degree.
100
A simple graph has no arrows and no multiple edges. What is the third thing it is not allowed to have?
Loops.
100
What do we call a drawing of a network in which no edges cross?
A planar representation.
100
In Euler's formula, and say what v, f and e stand for.
v + f − e = 2. v is the vertices, f is the faces, e is the edges.
100
A trail and a path are both walks with a rule about repeating. What is each one not allowed to repeat?
A trail must not repeat an edge. A path must not repeat a vertex.
200
A vertex has one loop and two edges going to other vertices. What is its degree?
4. A loop has both ends at the same vertex, so it counts twice.
200
How many edges does the complete graph K₄ have?
6. Four vertices, and each one is joined to the other three, so every vertex has degree 3. The degrees total 4 × 3 = 12, and that is twice the number of edges, so there are 6.
200
A network is drawn with two of its edges crossing. Does that prove the network is not planar? Explain.
No. Planar means a crossing-free drawing exists somewhere, even if this one isn't it.
200
A connected planar graph has 8 vertices and 12 edges. Give the number of faces.
6. (8 + f − 12 = 2.)
200
What do we call a closed path?
A cycle.
300
A vertex has no edges touching it at all. What is this vertex called, and what is its degree?
An isolated vertex, degree 0.
300
Is every complete graph also a simple graph? Explain your answer.
Yes. A complete graph is defined as a simple graph in which every pair is joined.
300
How many faces does this drawing have?
4. Three triangles inside, plus the outside.
300
A student says their planar drawing has 6 vertices, 10 edges and 5 faces. Check it, and say what they have most likely done.
6 + 5 − 10 = 1, not 2 — they are one face short, and have forgotten the outside. (With it counted: 6 + 6 − 10 = 2.)
300
Is the route A, B, D, E, C, A a walk, a trail, a path, a circuit or a cycle? Give the most exact name.
A cycle. Closed, no edge twice, no vertex twice except A at the ends.
400
Work out the total weight of this network.
34. 6 + 9 + 4 + 7 + 5 + 3. A loop carries weight like any other edge.
400
Do these two drawings show the same network? Which check gives you the answer?
No. Comparing the degree of each vertex by name. Both have 5 vertices and 6 edges, so those checks don't help — but P has degree 3 in drawing 1 and degree 2 in drawing 2.
400
Name a network that can never be drawn without edges crossing, no matter how you move the vertices.
K₅. Three houses joined to three services also works.
400
A map has 11 towns joined by 18 roads, and no road crosses another. Into how many regions is the map divided, counting the outside?
9. (11 + f − 18 = 2.)
400
The route A, B, D, E, B, C, A is a circuit. Explain why it is not a cycle.
Because B is visited twice in the middle of the route.
500
A network cannot have exactly three vertices of odd degree. Explain why not.
Because the degrees always add to an even number, and three odd numbers add to an odd number. Every edge adds 2 to the degree total.
500
In a complete graph, every vertex has degree 6. How many vertices does the graph have, and how many edges?
7 vertices and 21 edges. Joined to 6 others means 7 altogether; degrees total 42, which is twice the edges.
500
How many faces does this drawing have?
4. The gap between the two A–B edges, the triangle, inside the loop at C, and the outside.
500
A connected planar network has 9 vertices: four of degree 3 and five of degree 4. How many faces does a planar representation have?
9. (Degrees total 4×3 + 5×4 = 32, so 16 edges. Then 9 + f − 16 = 2.)
500
Find the shortest path from A to E. Write down every route you checked and its total.
A, B, D, E = 9.