language of graphs

Question 1

vertex

Answer 1

shown as a point on a graph
sometimes labelled, sometimes not

Question 2

edge

Answer 2

a line or curve with a vertex at each end

Question 3

walk

Answer 3

a set of edges joined end to end, so the end vertex of one edge is the start vertex of the next

Question 4

trail

Answer 4

a set of edges joined end to end, that does not repeat an edge
can repeat vertices although often do not

Question 5

cycle

Answer 5

a trail that starts and finishes at the same vertex. other than the start being the same as the finish, vertices are not repeated in a cycle

Question 6

adjacent

Answer 6

two vertices are directly connected if there is a edge with these vertices at its end

Question 7

connected

Answer 7

a graph is connected if it is possible to get from any vertex to any other, directly or indirectly

Question 8

loop

Answer 8

an edge that directly connects a vertex to itself

Question 9

multiple edge

Answer 9

when there is more than one edge that directly connect the same pair of vertices

Question 10

simple graph

Answer 10

a graph with no loops and no multiple edges

Question 11

degree

Answer 11

the degree of a vertex is the number of edges that end at that vertex

Question 12

subgraph

Answer 12

a graph formed by using some or all of the vertices of a graph together with some or all of the edges that connect these vertices.
a graph contained within another graph. this could result in an unconnected vertex however they are usually connected

Question 13

subdivision

Answer 13

inserting a vertex of degree 2 into an edge. increases the number of vertices by one and the number of edges by one

Question 14

complete graph

Answer 14

a simple graph on a given number of vertices, with the maximum possible number of edges. each vertex is connected by a single edge of the other vertices. the complete graph with n vertices is denoted by Kn AND HAVE 1/2 n(n-1) edges

Question 15

bipartite graph

Answer 15

a simple graph that can be partitioned into two sets so that every edge joins a vertex from one of these sets to a vertex in the other set. no edge connects two vertices in the same set

Question 16

complete bipartite graph

Answer 16

each vertex in the first set is connected by a single edge to each vertex in the second set. the complete graph with m vertices in the first set and n vertices in the second set is denoted by Km,n and has mn edges

Question 17

adjacency matrix

Answer 17

shows the number of edges that directly connect each pair of vertices

Question 18

complement

Answer 18

the complement of a simple graph is the set of edges that when added to the graph make a complete graph

Question 19

simple-connected graph

Answer 19

a graph that is both simple and connected

Question 20

tree

Answer 20

a simple connected graph with the minimum possible number of edges

Question 21

traversable graph

Answer 21

a graph that can be drawn as a trail, without going over the same edge twice

Question 22

eulerian graph

Answer 22

a connected graph that has no vertices of odd degree. they are traversable, with the trail starting and finishing at the same vertex

Question 23

semi-eulerian graphs

Answer 23

a connected graph that has exactly two vertices of odd degree, they are traversable, but the trail starts at one vertex and finishes at a different vertex

Question 24

hamiltonian graph

Answer 24

a graph that contains a cycle that passes through every vertex exactly once, apart from starting and finishing at the same vertex. the cycle is called a hamiltonian cycle. there will usually be edges in the graph that are not used in the cycle