Introductory To Graphs

Question 1

two vertices x, y ∈ V are adjacent

Answer 1

xy is an edge.

Question 2

v is said to be incident on
e and e is said to be incident on v.

Answer 2

vertex v is an endpoint of the edge e

Question 3

loop

Answer 3

an edge that joins the vertex v with
itself.

Question 4

proper edge

Answer 4

an edge that joins two different endpoints

Question 5

simple graph

Answer 5

A graph with no loops

Question 6

G′ = (V
′
, E′
) is called subgraph of G

Answer 6

if V
′ ⊆ V and E
′ ⊆ E

Question 7

spanning subgraph of the graph G

Answer 7

a subgraph that contains all the
vertices of G

Question 8

graph G is called complete

Answer 8

if xy ∈ E for all x, y ∈ V , x ̸= y

Question 9

degree of a vertex v

Answer 9

the number of edges of G incident on v

Question 10

trail

Answer 10

a walk in which all the edges (but not necessary the vertices)
are distinct.

Question 11

path

Answer 11

a walk in which all vertices (and implicitly all edges) are
distinct, except the first and the last, which can sometimes coincide.

Question 12

cycle

Answer 12

is a closed path

Question 13

distances between 2 vertices

Answer 13

the minimum of the lengths of all (x, y)