The user-friendly version of this content is available here.

The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.

This essential trains for: Math Kangaroo 5-6, Math Kangaroo 7-8, Math Kangaroo 9-10, AMC-10, AMC-12, AIME.

Theorem : The sum of the degrees of all the vertices in a graph is equal to twice the number of edges.

Proof: Each edge raises the degree of both vertices at its two ends. Therefore, each edge is counted twice when the sum of all the degrees is computed.

Fact: As a consequence, the sum of the degrees is always an even number.

Typical problem: In a bus network there are 3 stops where 5 lines arrive and 7 stops where are two lines. Is this network possible?

Answer: No, since the sum of all the degrees is an odd number:

equation


Eulerian graphs: An Eulerian graph can have no more than two odd vertices.

More specifically, if the path has an initial vertex that is different from the terminal vertex, then there can be two odd vertices, namely the first and the last vertices of the path. This is because edges go in as well as out at each vertex along the path, except for the first and last where it is possible to have only one edge (or, if entering that vertex multiple times, an odd number of incident edges.)

If an Eulerian path is a loop, then all vertices must be even.


Theorem: In a tree the number of vertices is one more than the number of edges.

equation

A simple path is a path on which each vertex occurs only once.

Theorem: In a tree graph, there is a unique simple path between any two vertices. This is faily obvious, because if there were two different simple paths from a certain vertex to another, then they would inevitably form a cycle and the graph would not be a tree. On the other hand, a path is guaranteed to exist since a tree is a connected graph.

Theorem: In a planar graph, Euler's equality is true:

equation

Where V is the number of vertices, F is the number of faces we get by drawing the non-intersecting graph and E is the number of edges.

Note that the 'outside' face is one of the faces that are counted.


It is sometimes useful in problem solving to have an already made planar graph of certain solids, so we don't have to think it up on the spot. Not all 3-D networks are planar, but the most commonly used in problems are the cube and the octahedron. For bugs that crawl on cubes and octahedrons, these are the planar representations you would use:

figure

The 'planar' cube is obtained by drawing a square face and then stretching out the square face that is opposite to it so that it is large enough to 'surround' the smaller face. Then, draw the remaining connecting edges.

figure

The 'planar' octahedron is obtained similarly, by choosing one of the triangular faces and the face opposite to it, like in this drawing. Shrink one of the shades faces to make the little interior triangle and stretch the other shaded face to make the large triangle that you see in the planar graph.

figure