Graph Theory

1

What is the formal name for the points on a graph?

1

What is the formal name for the lines connecting the points on a graph?

1

V =

1

E =

1

Two graphs are equal if and only if they have the same vertices and the same edges.

1

Two graphs are equal if and only if they have some vertices and the same edges.

1

We say that two graphs G and H are if we can relabel the vertices of G to obtain H.

1

The of a graph G is the number of vertices of G

1

The order of a graph G is the number of of G

1

The of G is the number of edges of G

1

The size of G is the number of of G

1

We often write ❌ as shorthand for an edge {u,v}

uv

{uv}

1

We often write uv as shorthand for an edge {}

1

We say that an edge e = uv is ( incident, adjacent ) to the vertices u and v.

1

If uv is an edge, we say that the vertices u and v are ( adjacent, incident )

1

u is a of v and that v is a neighbour of u.

1

For any vertex v of a graph G, the N(v) of v is the set of neighbours of v

1

For any vertex v of a graph G, the ............. of v is the set of neighbours of v

1

We say that v is isolated if it has no .

1

We say that v is ( isolated, complementary, distinct, incident, adjacent ) if it has no neighbours.

1

The neighbourhood of a is N(a) =

1

The neighbourhood of d is N (d) =

1

The neighbourhood of e is N(e) =

1

Vertex e is ........ vertex

1

Vertex e is an vertex

1

The degree of a vertex v in a graph G is d(v) = |N(v)|, that is,

1

d(v) =

1

The vertex degrees are
d(a) = ,
d(b) = ,
d(c) = ,
d(d) =
d(e) = .

1

If G is a graph with n vertices, then the degree of each vertex of G is an integer between 0 and n − 1.

1

If G is a graph with n vertices, then the degree of each vertex of G is an integer between and .

1

If G is a graph with n vertices, then the of each vertex of G is an integer between 0 and n − 1.

1

The sum of all vertex degrees is twice the number of edges

1

the sum of all vertex degrees is the number of edges

1

The sum of all vertex degrees is twice the number of

1

The sum of all vertex is twice the number of edges

1

In any graph there are an even number of vertices with odd degree.

1

In any graph there are an even number of edges with odd degree.

1

Any graph on at least two vertices has two vertices of the same .

1

The of a graph G is the sequence of all degrees of vertices in G

1

The of a graph G, denoted δ(G), is the degree of a vertex of G.

1

The of a graph G, denoted ∆(G), is the of a vertex of G.

1

A graph G is if every vertex of G has the same degree

1

We say that G is k-regular to mean that every vertex has degree k.

1

We say that G is -regular to mean that every vertex has degree k.

1

We say that G is to mean that every vertex has degree k.

1

A graph H is a of a graph G if we can obtain H by deleting vertices and edges of G.

1

A graph H is a subgraph of a graph G if we can obtain H by vertices and edges of G

1

H is a ( spanning, "blank", copy ) subgraph of G if additionally V (H) = V (G), that is, if only edges were deleted.

1

H is a ( subgraph, graph, spanning subgraph, copy ) of a graph G if we can obtain H by deleting vertices and edges of G.

1

Let G be a graph with δ(G) ≥ 2. Then G contains a cycle.

1

Let G be a graph with δ(G) ≥ 0. Then G contains a cycle.

1

Let G be a graph with N(G) ≥ 2. Then G contains a cycle.

1

Any graph with n vertices and at least n edges contains a cycle

1

Any graph with n vertices and at least n-1 edges contains a cycle

1

Any graph with n+1 vertices and at least n edges contains a cycle

1

The length of W is the number of ( edges, vertices ) traversed

1

A walk is closed if the first and last vertices of the walk are the same, that is, if you finish at the same vertex at which you started.

1

A walk is open if the first and last vertices of the walk are the same, that is, if you finish at the same vertex at which you started.

1

A walk is a path if and only if it has no repeated vertices

1

walk is a path if and only if it has repeated vertices

1

A closed walk is a cycle if and only if the only repeated vertex is the first and last vertex

1

A closed walk is a cycle if and only if there is a repeated vertex at the first and last vertex

1

A graph G is if for any two vertices u and v of G there is a walk in G from u to v.

1

A ❌ of G is a maximal connected subgraph of G

connected component

component

subgraph

tree

cycle

1

A tree is a ❌ ❌ graph.

connected

component

walk

path

unconnected

join

acyclic

walks

paths

cyclic

1

A ❌ of a tree is a vertex v with d(v) = ❌.

leaf

edge

vertex

1

2

0

5

1

Any tree on n ≥ 2 vertices has a leaf.

1

Any tree on n ≥ 0 vertices has a leaf.

1

Any connected graph contains a spanning tree

1

Any connected graph on n vertices with precisely n − 1 edges is a tree

1

Any connected graph on n vertices with precisely n edges is a tree

1

Any acyclic graph on n vertices with precisely n − 1 edges is a tree.

1

Any acyclic graph on n vertices with precisely n edges is a tree.

Bachelors Degree Mathematics Test sobre Graph Theory, creado por Will Rickard el 04/01/2016.