Key Terminology

Front 1

an edge associated to a set {u, v}, where u
and v are vertices

Back 1

undirected edge

Front 2

an edge associated to an ordered pair (u, v),
where u and v are vertices

Back 2

directed edge

Front 3

distinct edges connecting the same vertices

Back 3

multiple edges

Front 4

an edge connecting a vertex with itself

Back 4

loop

Front 5

an undirected graph with no multiple edges or loops

Back 5

simple graph

Front 6

an undirected graph that may contain multiple edges but no loops

Back 6

multigraph

Front 7

and undirected graph that may contain multiple edges and loops

Back 7

pseudograph

Front 8

a set of vertices together with a set of directed edges each of which is associated with an order pair of vertices

Back 8

directed graph

Front 9

a graph with directed edges that may contain multiple directed edges

Back 9

directed multigraph

Front 10

a directed graph without loops or multiple directed edges

Back 10

simple directed graph

Front 11

adjacent

Back 11

two vertices are adjacent if there is an edge between them

Front 12

incident

Back 12

an edge is incident with a vertex if the vertex is an endpoint of that edge

Front 13

deg v(degree of the vertex v in an undirected graph)

Back 13

the number of edges incident with v with loops counted twice

deg = 2*|E|

Front 14

deg v-

Back 14

edges coming in

Front 15

deg v+

Back 15

edges going out

Front 16

how many vertices does Kn have?

Back 16

n vertices

Front 17

how many edges does Kn have?

Back 17

n(n-1)/2

Front 18

how many vertices does Cn have?

Back 18

n

Front 19

how many edges does Cn have?

Back 19

n

Front 20

how many vertices does Wn have?

Back 20

n+1

Front 21

how many edges does Wn have?

Back 21

2n

Front 22

how many vertices does Km,n have?

Back 22

m+n

Front 23

how many edges does km,n have?

Back 23

m*n

Front 24

How many vertices does Qn have?

Back 24

2^n

Front 25

How many edges does Qn have?

Back 25

n*2^(n-1)

Front 26

For which values of n is Kn bipartite?

Back 26

1 or 2

Front 27

For which values of n is Cn bipartite?

Back 27

even

Front 28

For which values of n is Wn bipartite?

Back 28

none

Front 29

For which values of n is Qn bipartite?

Back 29

all values of n

Front 30

Let G = (V, E) be a graph.

A sequence of vertices v0, v1, . . . , vn in V
such that {vi−1, vi} ∈ E for i = 1, 2, . . . n is:

Back 30

A path

Front 31

A path where v0 = vn is called a

Back 31

circuit

Front 32

A path of length n is a path with

Back 32

n edges

Front 33

A path is simple if

Back 33

no vertex or edge is repeated

(with the exception of the first and last vertex).

Front 34

A simple path which is also a circuit is called a

Back 34

cycle

Front 35

A simple graph is called connected if

Back 35

there is a path between any two distinct vertices

Front 36

If G is a connected graph, then there is a

Back 36

simple path between every pair of distinct points.

Front 37

The maximally connected subgraphs of a graph G are called:

Back 37

the connected components of G

Front 38

If one can remove a vertex and all edges incident to it and produce a graph with more connected components than the original graph, then we call that vertex a

Back 38

cut vertex

Front 39

A graph without cut vertices is called

Back 39

non-separable

Front 40

If one can remove an edge and produce a graph with more connected components than the original graph, then we call that edge

Back 40

a cut edge

Front 41

A connected multigraph has an Euler path (which is not an Euler
circuit) if and only if it has exactly two vertices of

Back 41

odd degree

Front 42

A connected multigraph has an Euler circuit if and only if each of
its vertices has

Back 42

an even degree

Front 43

A Euler path in a multigraph G is a path that traverses every edge
exactly

Back 43

once

Front 44

An Euler path which is also a circuit is called an
Euler

Back 44

circuit

Front 45

A _______________ is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge

Back 45

complete graph

Front 46

If two simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic, then the following are true:

Back 46

Same number of vertices

Same number of edges

Corresponding vertices have same degree

If one is bipartite so is the other

If one is a complete graph so is the other

If one is a complete bipartite so is the other

If one has Cn cycles then so does the other.