# Further Maths - Graphs

> Source: https://ollybritton.com/notes/a-level/further-maths/topics/graphs/ · Updated: 2021-10-13 · Tags: school, further-maths, decision

## See Also
- [Further Maths - Eulerian Trails](https://ollybritton.com/notes/a-level/further-maths/topics/eulerian-trails/)
- [Further Maths - Hamiltonian Cycles](https://ollybritton.com/notes/a-level/further-maths/topics/hamiltonian-cycles/)
- [redacted](https://ollybritton.com/404)

## Flashcards
##### What is a graph with weighted edges called??
A network.

##### What is the degree of a vertex??
The number of edges connected to it.

##### What is the order of a vertex??
The number of edges connected to it.

##### What is the valency of a vertex??
The number of edges connected to it.

##### What is the sum of degrees of all vertices in a graph??
Double the number of edges.

##### What is the property called when two graphs have the same vertices and edges??
They are isomorphic.

##### ![PHOTO ISOMORPHIC GRAPHS](isomorphic-graphs.png) What is true about all these graphs??
They are isomorphic.

##### How can you show two graphs are isomorphic??
Match up vertex degrees and the edge set.

##### What is a walk in relation to graphs??
A sequence of edges where the end vertex of one edge is the start vertex of the next.

##### What is a trail in relation to graphs??
A walk where none of the edges are repeated.

##### What is a path in relation to graphs??
A trail where none of the vertices are repeated.

##### What is a cycle or circuit in relation to graphs??
A path that joins back up to the beginning.

##### What is a simple graph??
One with no loops and no double-edges.

##### ![PHOTO COMPLICATED GRAPH](complicated-graph.png) Why is this graph not simple??
Because it has a loop.

##### What does it mean for two vertices to be connected??
There is a path between them.

##### What does it mean for a graph to be connected??
All pairs of vertices are connected.

##### What is a tree??
A connected graph with no cycles.

##### What is a complete graph??
One in which every possible pair of vertices is connected by an edge.

##### What is the notation for the complete graph with $n$ vertices??
$$
K_n
$$

##### What is the formula for the number of edges for $K_n$ (the complete graph with $n$ verticies)??
$$
\frac{1}{2}n(n-1)
$$

##### What is a planar graph??
A graph that can be drawn so that none of the arcs cross.

### 2021-10-22
##### What is the order of the 4 ways you can get around a graph, going from least restrictive to most restrictive??
* Walk
* Trail
* Path
* Cycle

### 2021-11-04
##### What two things do you need to define a graph??
* Vertex set
* Edge set

### 2021-11-07
##### What degree does a loop contribute to a vertex??
$$
2
$$

##### What is a bipartite graph??
Graphs that consist of two or more independent sets of verticies that have no connections between themselves.

##### ![PHOTO BIGRAPH](bigraph.png) What is this an example of??
A bigraph.

### 2022-05-16
##### How can you remember that a trail is where no edge is visited more than once??
It's an "Eulerian trail", not "Eulerian path".

##### What are paths, trails and cycles all subsets of??
Walks.

##### What is a path??
A walk in which no vertex is visited more than once.

##### What is a cycle??
A walk in which the start and ends are the same.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt