# Graph theory definitions

HideShow resource information
Graph
A ----- is a network of dots ( vertices ) connected by lines ( edges ).
1 of 54
Degree of a vertex
The ------ -- - ------ is the number of edges connected to the vertex, counting any loop as connected twice
2 of 54
Multiple edges
Two or more edges linking the same pair of vertices are called ------- -----
3 of 54
Loops
An edge joining a vertex to itself is called a ----
4 of 54
Simple graph
A ------ ----- is one that has no loops or multiple edges.
5 of 54
Adjacency
Two vertices V and W of a graph are -------- if they are linked by an edge E.
6 of 54
Incidence
An edge E is -------- with the vertices it touches.
7 of 54
Isomorphism
Two graphs G and H are ---------- if H can be obtained by re-labeling the vertices of G.
8 of 54
Subgraph
A -------- H of a graph G is a graph all of whose vertices are of G and all of whose edges are of G
9 of 54
Degree Sequence
The ------ -------- of a graph G is the sequence obtained by listing the vertex degrees of G in ascending order, with repeats as necessary.
10 of 54
Walk
A ---- of length K is a succession of k edges. (for example a walk of length 3 could be denoted AB,BC,CD)
11 of 54
Trail
A ----- is a walk in which all the edges but not necessarily the vertices are different.
12 of 54
Path
A ----is a walk in which all the edges AND all the vertices are different.
13 of 54
Connectivity
A graph is --------- if there is a path between any two of its vertices. Otherwise it is disconnected.
14 of 54
Disconnected graph
Any ------------ ----- is the union of connected subgraphs, called components
15 of 54
Bridge
An edge in a connected graph is a ------ if it's deletion leaves a disconnected graph
16 of 54
Closed Walk
A ------ ---- in a graph is a walk that starts and ends at the same vertex.
17 of 54
Closed Trail
A ------ -----l is a closed walk in which all the edges are different.
18 of 54
Cycle
A ----- is a closed walk in which all the edges and all intermediate vertices are different.
19 of 54
Regular Graph
A graph is -------if it's vertices all have the same degree. A ------- ----- is r-regular if the degree of each vertex is r.
20 of 54
Tree
A ---- is a connected graph with no cycles.
21 of 54
Eulerian trail
A -------- ----- is a closed trail containing every edge of graph G
22 of 54
Eulerian Graph
A -------- ----- is a graph for which an Eulerian trail exists
23 of 54
Semi-Eulerian
A non Eulerian graph G is ----_-------- if there is an open trail containing every edge of G
24 of 54
Digraph
A directed graph ( or -------) D consists of a non-empty vertex set V and a finite family A of ordered pairs vw of vertices v,w that are elements of the set V , called arcs.
25 of 54
Simple Digraph
A digraph D is a ------ ------- if the arcs of D are all distinct and there are no loops.
26 of 54
Connected Digraphs
A digraph is connected if it's underlying graph is connected.
27 of 54
Strongly connected
A digraph D is -------- --------- if for any two vertices v,w that are a part of D there is a path from v to w on the digraph.
28 of 54
Orientability
A graph G is ---------- if each edge of G can be directed such that the resulting digraph is strongly connected.
29 of 54
Eulerian Digraph
A connected digraph D is -------- if there exists a trail containing every arc of D
30 of 54
Outdegree of a vertex
The --------- -- - ------ v is the number of arcs VW. The In-degree is the number of arcs WV.
31 of 54
Hamiltonian digraph
A digraph D is ----------- if there is a cycle that includes every vertex of D.
32 of 54
Semi-Hamilitonian
A digraph D is ----_----------- if there is a path that passes through every vertex of D
33 of 54
Tournament
A ---------- is a digraph in which any two vertices are joined by exactly one arc.
34 of 54
Forest
A ------ is a (not necessarily connected) graph with no cycles
35 of 54
Cycle rank
The number of edges removed in the procedure ( of removing cycles one edge at a time ) is the ----- ---- ( gamma ) of G.
36 of 54
Cutset Rank
The number of edges in a spanning tree is the ------ ---- (Xi) of G
37 of 54
Planar Graphs
A ------ ----- is a graph that can be drawn in the plane without crossings. ( may also be called a plane graph)
38 of 54
Crossing number
The -------- ------ cr(G) of a graph G is the minimum number of crossings that can occur when G is drawn in the plane
39 of 54
Homeomorphicity
Two graphs are ------------ if both can be obtained from the same graph by inserting additional vertices of degree 2 into it's edges.
40 of 54
Contractible
A graph G is ------------ to another graph H' if H' can be obtained by successively contracting edges of H. That is, by removing an edge and identifying it's end vertices
41 of 54
Faces
If G is a planar graph then any plane drawing of G divides the points on the plane that are not on G into regions- called -----. One of these faces is unbounded it is called the infinte face.
42 of 54
Face Degree
Let G be a connected planar graph, and F be any face of a plane drawing of G. Then the degree of F, written deg(F) is the number of edges of the boundary of face F
43 of 54
k-colourable
A graph G ( without loops ) is -_---------- if you can assign one of k colours to each vertex so that adjacent vertices have different colours
44 of 54
Chromatic number
If G is k-colourable but not (k-1)-colourable then we call G k-chromatic and it's --------- ------ ( chi of G ) is k
45 of 54
Map
A --- is a 3-connected plane graph
46 of 54
Colouring of maps
a map is k colourable if it's faces can be coloured with k colours such that no two faves with a common boundary edge have the same colour
47 of 54
k-edge-connectivity
Graph G is -_----_--------- if the smallest number of edges that must be deleted to disconnect G is >= k . ( i.e any cutset of G has >= k edges)
48 of 54
k-connectivity
Graph G is -_--------- if the smallest number of vertices that must be deleted to disconnect G is >= k
49 of 54
Network
A ------- N is a weighted digraph where each arc, a , is assigned a positive number ( psi(a)) called it's capacity.
50 of 54
A cut in a network
A --- -- - ------- is a set A of arcs such that each path from v to w includes and arc in A. A cut is a vw-disconnecting set.
51 of 54
Capacity of a cut
The -------- -- - --- is the sum of the capacities of the arcs in A
52 of 54
Minimum cut
A ------- --- is a cut with minimal capacity
53 of 54
Complete matching
A -------- -------- from A to B in a bipartite graph G(A,B) is a one to one correspondence between the vertices in A and a subset of vertices in B such that corresponding vertices are joined.
54 of 54

## Other cards in this set

### Card 2

#### Front

The ------ -- - ------ is the number of edges connected to the vertex, counting any loop as connected twice

#### Back

Degree of a vertex

### Card 3

#### Front

Two or more edges linking the same pair of vertices are called ------- -----

#### Back ### Card 4

#### Front

An edge joining a vertex to itself is called a ----

#### Back ### Card 5

#### Front

A ------ ----- is one that has no loops or multiple edges.

#### Back ## Comments

Report

I just wanted to say that the gaps are usually just the word on the front, but it makes them possible to use the crossword feature :)

## Similar Mathematics resources:

See all Mathematics resources »See all Graph theory resources »