Section 1: Fundamentals

Question 1

Graph

Answer 1

A pair (V, E), where V is any finite set, and E is a set whose elements are pairs of elements from V

Question 2

Vertex set

Answer 2

The set V in (V, E), sometimes written V(G)

Question 3

Edge set

Answer 3

The set E in (V, E), sometimes written E(G)

Question 4

Adjacent vertices

Answer 4

there is an edge between them

Question 5

Endpoints of an edge

Answer 5

the vertices connected by the edge

Question 6

incident

Answer 6

If e = uv is an edge of G, we say that u and v are
incident with e, and if two edges e and f have a common endpoint we
say that e and f are incident.

Question 7

Adjacency matrix

Answer 7

an n × n matrix in which , the entry in the column labelled u and the row labelled v is 1 if and only if uv is an edge.

Question 8

Multigraphs

Answer 8

Graphs with loops and/or multiple edges

Question 9

Directed graph/ Digraph

Answer 9

A graph where all the edges are directed from
one vertex to another.

Question 10

Formally, a digraph G is a pair (V, E), where V is any finite set, and E is a set whose elements are …

Answer 10

ordered pairs of elements from V.

Question 11

Weighted graph

Answer 11

each edge is given a weighting indicating the
strength of the interaction the edge represents

Question 12

Subgraph

Answer 12

a graph H obtained from G by deleting vertices and/or edges

Question 13

Induced subgraph

Answer 13

a subgraph H of G obtained by deleting only vertices (and the edges incident with the deleted vertices).

Question 14

Thus, if U is a subset of the vertices, we can refer to the subgraph induced by U: this is the graph
with …..

Answer 14

vertex-set U and edge-set {vw ∈ E : v, w ∈ U}.

Question 15

Spanning subgraph

Answer 15

a subgraph of G obtained by deleting only edges.

Question 16

Walk from u to v

Answer 16

a sequence of vertices w1, . . . , wp (for some natural number p ≥ 2), with w1 = u and wp = v, such that wiwi+1 is an edge for every 1 ≤ i ≤ p − 1.

Question 17

Path from u to v

Answer 17

a walk from u to v in which all the vertices
w1, . . . , wp are distinct.

Question 18

Connected graph

Answer 18

if, for every two distinct vertices u, v ∈ V, there is a path in G from u to v

Question 19

Disconnected graph

Answer 19

Graph that is not connected

Question 20

Connected component

Answer 20

We say that a subgraph H of G is a connected component of G if H
is a maximal connected subgraph of G

Question 21

Degree of vertex

Answer 21

Number of edges incident with the vertex

Question 22

In a simple graph on n vertices, the degree of a vertex cannot be more than

Answer 22

n − 1

Question 23

Minimum degree

Answer 23

min_(v∈V(G))d(v)

Question 24

Maximum degree

Answer 24

max_(v∈V(G))d(v)

Question 25

Isolated vertex

Answer 25

A vertex of degree zero

Question 26

Degree sequence

Answer 26

A list of all of the degrees of the vertices in the graph, often listed in increasing order

Question 27

Isomorphic graphs

Answer 27

if one graph can be obtained from the other by changing the labels

Question 28

Isomorphism from G1 = (V1, E1) to G2 = (V2, E2)

Answer 28

a bijection f : V1 → V2 such that, for every u, v ∈ V1, f(u)f(v) ∈ E2 if and only if uv ∈ E1

Question 29

there is an isomorphism from G1 to G2 if and only if ….

Answer 29

there is an isomorphism from G2 to G1.

Question 30

If G1 and G2 are isomorphic, then:
* G1 and G2 have the same number of ___ and the same number of ____

Answer 30

vertices and edges,

Question 31

If G1 and G2 are isomorphic, then:
G1 and G2 have the same

Answer 31

degree sequence

Question 32

If G1 and G2 are isomorphic, then:
G1 is connected if and only if …

Answer 32

G2 is connected

Question 33

Complete graph

Answer 33

a complete graph on n vertices, denoted Kn, is a graph on n vertices in which every pair of distinct vertices forms an edge.

Question 34

Clique

Answer 34

Complete graph

Question 35

How many edges does K_n have?

Answer 35

(n )
(2 ) = 1/2n(n − 1) edges.

Question 36

Path on n vertices, denoted P_n

Answer 36

a graph that is isomorphic to the graph (V, E) where V = {v1, . . . , vn} and E = {vivi+1: 1 ≤
i ≤ n − 1}

Question 37

Endpoints of path

Answer 37

The vertices corresponding to v1 and vn in Pn

Question 38

How many edges does a path have?

Answer 38

n − 1

Question 39

Cycle on n vertices, denoted C_n

Answer 39

s a graph that is isomorphic to the graph (V, E) where V = {v1, . . . , vn} and E = {vivi+1 : 1 ≤ i ≤ n − 1} ∪ {vnv1}.

Question 40

Notice that Cn can be obtained from Pn by adding

Answer 40

one extra edge
between the endpoints of the path

Question 41

How many edges does a cycle have?

Answer 41

n