Block 1 Graphs

Question 1

Order (n)

Answer 1

number of vertices |V|

Question 2

Size (m):

Answer 2

number of edges |E|

Question 3

Isolated vertex

Answer 3

Degree 0

Question 4

Sum of degrees /2

Answer 4

Number of edges

Question 5

Eulerian cycle:

Answer 5

Exists if and only if the graph is connected and each vertex is incident to a even number of edges.

Question 6

Neighbourhood

Answer 6

is the set of vertices adjacent to it

Question 7

Close Neighbourhood

Answer 7

is the Neighbourhood and the vertex in question

Question 8

Kn

Answer 8

Complete graph, n vertices

Question 9

On

Answer 9

Empty graph, n vertices

Question 10

Cn

Answer 10

Simple Cycle. n>3

Question 11

Pn

Answer 11

Simple Path. n>2. The same as a Cn but one edge missing. Simple Path. n>2. The same as a Cn but one edge missing.

Question 12

k-regular

Answer 12

: all vertices (k) are of the same degree.

Question 13

Wn

Answer 13

wheels

Question 14

Bipartite graph

Answer 14

When there exists a partion of vertice in two parts (A and B) such that there is no edges in each partion, just between them. The sets A and B may be empty.

Question 15

Complete bipartite graph

Answer 15

a vertex in one partition group is adjacent to all vertices in the other partition group.

Question 16

Equal graphs

Answer 16

Must have the same labels. V(G) = V(H) and E(G) = E(H).

Question 17

Isomorphic graphs (≅):

Answer 17

Two graphs are isomorphic if there is a bijection and adjacency/ non adjacency is preserved. Bijection: Surjective (all vertices in the codomain are used) and Injective (1 to 1 – can’t have 1 vertex mapped to two). Top Tip: Pay attention at the structure: Degree of vertices, if there exists a triangle inside? Cycle?

Question 18

Proper subgraph

Answer 18

H⊆G but H≠G

Question 19

Spanning subgraph

Answer 19

Vertice set is equal. V(S)=V(G)

Question 20

Improper subgraph

Answer 20

Every graph is a subset of itself