AS Further Maths: Decision

Chapter 1:

Chapter 2: Explain why a network cannot have an odd number of vertices of odd degree. [2marks]

The number of vertices is equal to double the number of edges, and when any number is doubles it is even

What is meant by a vertices/nodes?

The points where the lines which connect the edges (lines)

What is meant by edges/arcs?

The lines that are connect by nodes/vertices

What is meant by the order/degree/valency of each vertex?

It is the number of edges meeting at one vertex

Is there a vertex where two edges interesect?

Not always, where two edges intersect doesn’t mean that a vertex must be there

What is meant by a walk?

A route from one vertex to another

What is meant by a path?

A walk where no vertex is visited more than once

What is meant by a cycle?

A path that ends where it started

What is meant by a Hamiltonian cycle?

A cycle that visits all vertices

What is meant by a trail?

A walk where no edge is visited more than once

What is meant by a Eulerian circuit?

A trail that ends where it started

State Euler’s Handshaking Lemma

The sum of degrees of the vertices is equal to double the number of edges

How many edges does a loop count as?

2 edges

What is meant by a tree?

A connected graph with no cycles

What is meant by a spanning tree?

A tree that is a subgraph and contains all vertices from the original graph