Graph Theory

Question 1

What a is a vertex

Answer 1

it is a point on the graph

Question 2

What is an edge

Answer 2

Is a line or a curve with a vertex at each end

Question 3

What does it mean when two vertices are adjacent

Answer 3

If they are connected by an arc

Question 4

What is a loop

Answer 4

An arc that connects a vertex to itself is called a loop

Question 5

What is a directed graph

Answer 5

A graph where at least one edge has a direction associated with it

Question 6

What is a network

Answer 6

A graph where each edge has a number or weight associated with it

Question 7

What does it mean when a graph is connected to

Answer 7

When it is possible to get from any vertex to any other vertex directly or indirectly

Question 8

What does it mean when a graph is simple

Answer 8

If there is only ever one arc between two adjacent vertices and no loops

Question 9

What a simply connected graph

Answer 9

A graph that is connected and simple

Question 10

What is the degree

Answer 10

The number of edges that join a vertex with a loop counting twice

Question 11

What are indegrees and outdegrees

Answer 11

The indegree is the number of edges leading to the vertex and the outdegree is the number of edges leading from the vertex

Question 12

What are odd and even vertices

Answer 12

A vertex with an odd degree is called an odd vertex and an even vertice is a vertex with an even degree

Question 13

What is the sum of the vertices always

Answer 13

Even in graph theory

Question 14

What is a tree

Answer 14

A simply connected graph with the minimum number of arcs is called a tree

Question 15

What is a walk

Answer 15

A sequence of edges in which the end of one edge is the beginning of the next

Question 16

What is a trail

Answer 16

A walk with no repeated edges

Question 17

Hat is a closed trail

Answer 17

WA trail that starts and ends at the same vertex

Question 18

What is a path

Answer 18

A trail with no repeated vertices

Question 19

What is a cycle

Answer 19

A closed path

Question 20

What is a route

Answer 20

A general term referring to walk, trail or path, that can be closed or not closed.

Question 21

What is a complete graph

Answer 21

A graph where every vertex is connected to every other vertex

Question 22

What is a complete graph denoted as

Answer 22

Kn

Question 23

What is the formula for the number of arcs in a complete graph

Answer 23

1/2 (n)(n-1)

Question 24

What are bipartite graphs

Answer 24

When every vertex from the first set connects to a vertex from the second set

Question 25

What is a complete bipartite graph

Answer 25

A bipartite graph with the maximum number of arcs

Question 26

What is the denotion for a complete bipartite graph

Answer 26

Km,n has mn arcs

Question 27

What is the colouring algorithm to show whether a graph is bipartite

Answer 27

Step 1. Choose any vertex as the starting vertex and colour it red Step 2. Colour every vertex that is adjacent to a red vertex as blue Step 3. Colour every vertex that is adjacent to a blue vertex as red Step 4. If a vertex is coloured both red and blue STOP; the graph is not bipartite

Question 28

What is a traversible graph

Answer 28

A graph that is one that cna be drawn without asking pen from paper, or going over the same graph twice

Question 29

What is an Eulerian graph

Answer 29

A graph where you can draw a closed trail covering every edge

Question 30

What is a semi-Eulerian graph

Answer 30

A graph that you can draw a trail that covers every edge, but none that’s closed is semi-Eulerian

Question 31

What is a Hamiltonian graph

Answer 31

A graph that contains a cycle that passes through every vertex exactly once

Question 32

What is ores theorem

Answer 32

For a simply connected graph with G with n>= 3 vertices, if the sum of the vertex degrees >= n for every pair of non-adjacent vertices then G is Hamiltonian

Question 33

What is a feature of ores theorem

Answer 33

It’s a sufficient condition not a necessary condition, so if the condition fails it’s inconclusive

Question 34

What is isomorphism in graphs

Answer 34

Two graphs are isomorphic if they share the same structure

Question 35

How can you tell if two graphs are isomorphic

Answer 35

If two graphs have different degree sequences then they aren’t isomorphic

Question 36

What is a digraph A

Answer 36

Graph with directed arcs

Question 37

What is the relationship between the in-degree and out-degree and the number of arcs

Answer 37

Total in degree = total out degree = number of arcs

Question 38

What is a subdivision

Answer 38

An insertion of vertex of degree two into an arc

Question 39

What is contraction

Answer 39

Means removing an arc from a graph and merging the two vertices previously joined. The new vertex’s label is a concatenation of the previous vertices names.