## Summary/Background

A graph is a set of points, called vertices or nodes, connected by lines called edges or arcs. A simple graph is one that has no loops and in which no pair of vertices are connected by more than one edge. The number of edges incident on a vertex is called its order, degree or valency.

## Software/Applets used on this page

This page uses Macromedia Flash. Your browser will need to have the Flash plugin installed - freely available from Macromedia. Flash movies designed by Helen Foster, Alton College, UK, and used with her permission.

## Glossary

### connected

of two vertices if there is a path between them.

### degree

On a graph: the number of edges incident to a vertex.

In geometry: a measure of angle

In geometry: a measure of angle

### edge

the line connecting two vertices of a graph, also known as arc or line.

### graph

A diagram showing a relationship between two variables.

The diagram shows a vertical y axis and a horizontal x axis.

The diagram shows a vertical y axis and a horizontal x axis.

### valency

The number of edges incident to a vertex.

### vertex

A point or node of a graph.

## This question appears in the following syllabi:

Syllabus | Module | Section | Topic | Exam Year |
---|---|---|---|---|

AQA A-Level (UK - Pre-2017) | D1 | Algorithms on graphs | Minimum connector | - |

AQA AS Further Maths 2017 | Discrete Maths | Networks | Minimum Connector | - |

AQA AS/A2 Further Maths 2017 | Discrete Maths | Networks | Minimum Connector | - |

Edexcel A-Level (UK - Pre-2017) | D1 | Algorithms on graphs | Minimum connector | - |

Edexcel AS Further Maths 2017 | Decision Maths 1 | Algorithms on Graphs | Minimum Connector | - |

Edexcel AS/A2 Further Maths 2017 | Decision Maths 1 | Algorithms on Graphs | Minimum Connector | - |

I.B. Higher Level | 10 | Algorithms on graphs | Minimum connector | - |

OCR A-Level (UK - Pre-2017) | D1 | Algorithms on graphs | Minimum connector | - |

OCR AS Further Maths 2017 | Discrete Maths | Network Algorithms | Minimum Connector | - |

OCR MEI AS Further Maths 2017 | Modelling with Algorithms | Networks | Minimum Connector | - |

OCR-MEI A-Level (UK - Pre-2017) | D1 | Algorithms on graphs | Minimum connector | - |

Universal (all site questions) | A | Algorithms on graphs | Minimum connector | - |