Flashcards in Definitions Deck (33):

1

## Handshaking Lemma

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

2

## Bipartite graph

###
A graph whose vertices can be divided into two sets such that no two vertices in the

same set are adjacent.

3

## Circuit

### A walk that begins and ends at the same vertex, and has no repeated edges.

4

## Complement of a graph G

###
A graph with the same vertices as G but which has an edge between any two

vertices if and only if G does not.

5

##
Complete bipartite

graph

###
A bipartite graph in which every vertex in one set is joined to every vertex in the

other set.

6

##
Complete graph

### A simple graph in which each pair of vertices is joined by an edge.

7

## Connected graph

### A graph in which each pair of vertices is joined by a path.

8

## Cycle

### A walk that begins and ends at the same vertex, and has no other repeated vertices.

9

## Degree of a vertex

###
The number of edges joined to the vertex; a loop contributes two edges, one for

each of its end points.

10

##
Disconnected graph

### A graph that has at least one pair of vertices not joined by a path.

11

## Eulerian circuit

### A circuit that contains every edge of a graph.

12

## Eulerian trail

### A trail that contains every edge of a graph.

13

## Graph

### Consists of a set of vertices and a set of edges.

14

##
Graph isomorphism

between two simple

graphs G and H

###
A one-to-one correspondence between vertices of G and H such that a pair of

vertices in G is adjacent if and only if the corresponding pair in H is adjacent.

15

## Hamiltonian cycle

### A cycle that contains all the vertices of the graph.

16

## Hamiltonian path

### A path that contains all the vertices of the graph.

17

## Loop

### An edge joining a vertex to itself.

18

##
Minimum spanning

tree

### A spanning tree of a weighted graph that has the minimum total weight.

19

## Multiple edges

### Occur if more than one edge joins the same pair of vertices.

20

## Path

### A walk with no repeated vertices.

21

## Planar graph

### A graph that can be drawn in the plane without any edge crossing another.

22

## Simple graph

### A graph without loops or multiple edges.

23

##
Spanning tree of a

graph

### A subgraph that is a tree, containing every vertex of the graph.

24

## Subgraph

### A graph within a graph.

25

## Trail

### A walk in which no edge appears more than once.

26

##
Tree

### A connected graph that contains no cycles.

27

## Walk

### A sequence of linked edges.

28

## Weighted graph

### A graph in which each edge is allocated a number or weight.

29

## Weighted tree

### A tree in which each edge is allocated a number or weight.

30

## Chinese postman problem

### To determine a cycle where each vertex is visited once only, returning to the original vertex of least total weight

31

## Travelling salesman problem

### To determine the shortest route that visits each vertex and returns to the original vertex, of least weight.

32

## Pigeon Hole Principle

### If kn+1 objects (where k, n are members of the positive integers) are divided into n groups, there will be a group that contains at least k+1 objects.

33