20240311: Graphs

Question 1

Graph

Definition

Unidrected Graph

Answer 1

A graph G is an ordered pair (V, E) consisting of a set of vertices and a set of edges, disjoint from V, together with an incidence function Ψ that associates with each edge an unoredered pair of not necessarily distinct vertices in V.

Question 2

Order and size of a graph G

Terminology; notation

Undirected Graph

Answer 2

• Order: the number of vertices in graph G (denoted by n or v(G))
• Size: the number of edges in graph G (denoted by m or e(G))

Question 3

True or false:

Adjacency happens between an edge and a vertex.

Answer 3

False.
Adjacency happens between two edges (sharing a vertex) or between two vertices (sharing an edge).

Question 4

True or false:

Incidence happens between two vertices or two edges.

Answer 4

False.
Incidence happens between an edge and its ends, or between a vertex and its edges.

Question 5

Neighbours of a vertex v

Terminology; notation

Undirected Graph

Answer 5

N_G(v): a set of neighbours of a vertex v in graph G.

Question 6

Loop; parallel edge

Terminology

Answer 6

Loop: an edge with identical ends.
Parallel edge: multiple edges with the same ends.

Question 7

Finite graph; null graph; trivial graph; simple graph

Terminology

Answer 7

• Finite graph: has finite sets of vertices and edges
• Null graph: no vertices
• Trivial graph: only one vertex
• Simple graph: no loops or parallel edges

Question 8

Complete graph; empty graph; bipartite graph

Terminology

Answer 8

• Complete graph: simple graph in which any two vertices are adjacent
• Empty graph: an empty edge set
• Bipartite graph: vertex set split in two, each edge connects a vertex from one part with a vertex in the other

Question 9

True or false:

A graph is complete bipartite if it is simple and every vertex from one part is connected to every vertex in the other part.

Answer 9

True. Example: Star, S_n

Question 10

Complete graph

Notation; characteristics

Answer 10

Complete graph: denoted by K_n
- number of vertices: n; number of edges: n over 2

Question 11

Bipartite graph

Notation; characteristics

Answer 11

• Bipartition denoted by (X, Y)
• Bipartite graph denoted by G[X, Y]
• Number of edges: 2^n

Question 12

Path

Terminology; notation

Answer 12

A simple graph whose vertices are arranged in a linear sequence so that two vertices are adjacent if they are consecutive in the sequence, and not otherwise.
- denoted by P_n
- number of vertices: n; number of edges: n-1 -> length

Question 13

Cycle

Terminology; notation

Answer 13

A simple graph on two or more vertices that can be arranged in a cyclic sequence, so that the rule for the path holds.
- denoted by C_n
- number of vertices/edges: n -> length

Question 14

True or false:

In a path or a cycle, parity is determined by the length.

Answer 14

True. The number of edges being odd or even determines the parity of the path or a cycle.

Question 15

When is a graph (dis)connected?

Answer 15

• Not connected: if the vertex set can be split in two parts such that there are no edges connecting vertices in different parts. Otherwise, connected.

Question 16

True or false:

Is every connected graph bipartite?

Answer 16

False. Every bipartite graph is connected, by the definition of connectedness. It does not hold in the other direction.

Question 17

Vertex degree

Terminology; notation

Undirected Graph

Answer 17

Vertex degree: number of neighbours (adjacent vertices); denoted by d(v)
- isolated vertex: d(v) = 0
- minimum degree: min. value of degrees in a graph; denoted by δ(G)
- maximum degree: max. value of degrees in a graph; denoted by Δ(G)
- average degree: d(G) = 1/2 sum d(v), sum over v in V

Question 18

True or false:

Every vertex degree of a regular graph is the same.

Answer 18

True. It is also called a k-regular graph, for some k = d(v), for all vertices.

Question 19

Isomorphism

Definition

Answer 19

Two graphs G and H are isomorphic if there is a bijection Θ: V(G) -> V(H), such that uv in E <=> Θ(u)Θ(v). They have the same n, m and degree sequence.

Question 20

True or false:

An unlabelled graph is a representative of an equivalence class of isomorphic graphs.

Answer 20

True

Question 21

Line graph

Definition; notation

Answer 21

A representation of G where the vertex set of a line graph is the edge set of G, and two edges are adjacent if they have an end in common; denoted by L(G).