Give me the equation for a graph
G = (V,E)
What is a ‘finite’ ‘simple’ graph
It’s a graph with finite vertices
Their are no loops nor multiple edges
What does it mean for two vertices to be adjacent?
They are connected by a edge.
So if u and v and adjacent then uv∈E
What does it mean if two edges are adjacent?
It means they must have a common vertex
What does it mean if a vertex and edge are incident?
If a vertex is an end point to an edge
What is the order of a graph?
The number of vertices in G
How is the order of a graph denoted?
|V|, |G|, n(G), n and can say an n-vertex graph
What does the size of a graph mean?
The number of edges
How is the size of a graph denoted?
|E|, m(G) or just m
What does ‘G is a (6,7)-graph mean?
A 6 vertices and 7 edges graph
What does the neighbourhood of a vertex mean?
For graph G, the neighbourhood of a vertex v is the set of vertices adjacent to v
How is the neighbourhood of a vertex denoted
N(v) or N⌄G(v)
What is the closed neighbourhood?
For a vertex, the set of all vertices that are adjacent to it including its own vertex
How is the closed neighbourhood of V denoted?
N(v)∪{v}
What is a complete graph and how is denoted?
A graph where any vertex is adjacent to any other vertex.
It is denoted K⌄n where n is the order of K
What is a empty graph and how is it denoted?
A graph with no edges and it is denoted as O⌄n where n is its order
What is a simple cycle graph and how is it denoted. What would n = 3 and n = 4 look like?
The example would be a triangle. C⌄4 would be a square
What is a simple path and its denotion?
It is denoted P⌄n and it is just a path of vertices and edges
What is a star and how is it denoted?
What would the graph where n = 3 look like?
A star graph has a single point which is adjacent to every other point
It is denoted S⌄n
One centre point then two around it
A star graph can be denoted in two different ways!
What is a wheel graph and how is it denoted?
A wheel graph is when you take a cycle Cn-1, add a new vertex called the hub then connect the hub to every vertex of the cycle
They are denoted as W⌄n
What is a bipartite graph?
When you can split its vertices into two sets so that no edge connects two vertices in the same set
Are the following graphs bipartite?
K⌄n, O⌄n, K⌄1,k, W⌄k
a) bipartite only if n is lower than or equal to 2. Larger creates odd cycles
b) yes, has no edges so cannot violate rules of bipartite
c) a star is always bipartite
d) wheels graphs always contain odd cycles so no
What is a complete bipartite graph?
If any vertex in A is adjacent to any vertex in B.
How is a complete bipartite graph notated?
K⌄p,q where p and q are the numbers of vertices in A and B, respectively
