How many edges are in the graph Kₙ,ₘ?
nm
How can edges be represented?
Tuples
Is the edge (1,2) ≡ (2,1)
Yes, the edges are unordered.
What is the degree of a vertex?
The number of edges conected to it
What is a degree sequence?
The number of vertices with a given degree.
What does the degree sequence q(1) = 1, q(2) = 3 mean?
There is 1 node with the degree 1, and 3 nodes with the degree 2
What is the degree distribution?
The probability for a vertex to have a given degree. eg. q(1) = 1/8, q(2) = 3/8 …
What is the neighbourhood?
The set of vertices adjacent it. eg. N(2) = {1,3,4,5}
What does N(v) denote?
The neighbourhood of a vertex v
How do you write a vertex and edge list?
List all vertices in the graph then list the edges as tuples. eg.
V = a,b,c,d,e
E = {(a,b), (a,c), (b,e), (c,d), (d,e)}
How do you write an adjacency list?
a | b,c
b | a,d,e
c | a,d
d | b,c,e
e | b,d
How do you write an incidence matrix?
Write the edges as tuples along the top, and the vertices down the right side. Then put 1s in the rows where the tuple above contains that vertex. eg.
(a,b) (a,c) (b,d)
1 1 0 a
1 0 1 b
0 1 0 c
0 0 1 d
Why are incidence matrices helful?
You can easily compute the degree of each vertex looking at the row
What is a complete graph?
When there is an edge between every pair of vertices.
How do you denote a complete graph on n vertices?
Kₙ
What is a cycle graph?
Where every node has exactly 2 edges so that the edges are {(v1,v2), (v2,v3), …, (vn,v1)}
What does Cₙ denote?
A cycle graph with n vertices
How many vertices does the graph Sₙ have?
n+1
What does Sₙ denote?
A star graph with n edges, n+1 vertices
What is a biparite graph?
Where the vertices can ve split into two sets where there are no edges between vertices in a set, only between vertices in different sets. eg.
0 0 0
I \ I \ / \
0 0 0 0
What is the handshaking leemma/degree sum formula?
The sum of the node degrees is twice the number of edges in the graph
What is a k-regular graph?
A graph where every vertex has k neighbours
What does it mean if a is incident to b?
There is an edge ab
What does it mean if 2 graphs are isomorphic?
They have the same number of verticies and edges and the same degree sequence
