How is edge deletion and vertex deletion of G denoted?
G-v is vertex deletion
G+e is edge addition
What is the union of two graphs G and H called and what is the vertex set and edge set going to be?
G∪H
V(G)∪V(H)
E(G)∪E(H)
When is G∪H said to be disjoint?
If V(G)∩V(H)=Ø
G and H do not share any vertices
What does 2K⌄2 stand for and is it disjoint?
K⌄2∪K⌄2
Yes
What is a walk?
A alternating sequence of vertices and edges
(v⌄1,e⌄1,v⌄2,e⌄2,…,e⌄k-1,v⌄k)
such that e⌄i = {v⌄i, v⌄i+1} where i=1,2,…, k-1
When is a graph connected?
If for any two distint vertices, u and v, there is a (u,v)- walk
Meaning that any point is connected to any other point with a walk along points or a single movement
Are these graphs connected: K⌄3, 2K⌄3?
yes
no
What is a (u,v) walk?
(u,v)-path?
simple (u,v)-path?
A (u, v)-walk is any sequence of vertices and edges that starts at vertex u and ends at vertex v
A (u, v)-path is a walk from 𝑢 to 𝑣 in which no vertex is repeated
This means exactly the same thing as a (u, v)-path
Is it true that a (u,v)-walk contains a (u,v)-path, a simple (u,v)-path?
yes
What is a connected componant of a graph g?
Its maximal connected subgraph. Every graph is the disjoint
union of its connected components.
What is a degree of a vertex?
The degree of a vertex v is the number of vertices in its neighbourhood
How is the degree of a vertex notated?
deg v = |N(v)|
What makes a vertex isolated?
A vertex v is isolated if deg v = 0
What a vertex a pendant?
A vertex v is pendant if deg v = 1
When is a vertex dominating?
A vertex v is dominating if deg v = |G(v) |-1.
What are the minimal and maximal vertex degrees of a graph G are denoted by?
∂(G) and Δ(G), respectively. E.g.
∂(K2,k)= and Δ(K2,k)= .
∂(K⌄2,k)= ?
Δ(K⌄2,k)= ?
2
k
What is the handshake Lemma?
State it in simple terms
It states that the sum of degrees of all vertices is an even number which is twice the size of E(G)
There as many total connections to vertices as there are edges times by 2
For any simple graph, the number of vertices of odd degree is what?
Even
What is the degree sequence of a graph?
Where the degree of all vertices of a graph are listed, typically put in descending order
Which graphs are specified by the degree sequence (2,…,2,1,1)= (2(k)
,1(2))?
A path, could be a long path, but has to be path. Loop type graphs dont work, only paths
What is the difference between degree of v and neighbourhood of v (+ example)
Neighbourhood is the vertexs that are adjacent to v and degree is how of those vertex
N(v) = {a,b,c}
deg(v) = 3
