Graphs

Question 1

What is a graph?

Answer 1

A set of vertices connected by edges.

Question 2

What is a walk?

Answer 2

A set of edges joined end-to-end.

Question 3

What is a trail?

Answer 3

A walk where no edges are repeated but vertices can be repeated.

Question 4

What is a cycle?

Answer 4

A trail that starts and ends at the same vertex.

No vertices can be repeated.

Question 5

What is a connected graph?

Answer 5

A graph where it is possible to get from any vertex to any other vertex.

Question 6

What is a simple graph?

Answer 6

A graph with no loops or multiple edges.

Question 7

What is a simple-connected graph?

Answer 7

A simple graph that is connected.

Question 8

What is a complete graph?

Answer 8

A simple graph with the maximum possible number of edges.

Question 9

How many edges does the complete graph with n vertices have?

Answer 9

0.5(n(n-1))

Question 10

What is a bipartite graph?

Answer 10

Simple graph.
Partitioned into two sets.
No edge connects two vertices in the same set.

Question 11

What is a complete bipartite graph?

Answer 11

A bipartite graph.

Each vertex is joined to each other vertex in the other set by 1 edge.

Question 12

How many edges does the complete bipartite graph with m vertices in the first set and n vertices in the second set have?

Answer 12

mn edges

Question 13

What does an adjacency matrix show?

Answer 13

The number of edges that directly connect each pair of vertices.

Question 14

What property does an adjacency matrix have about the lead diagonal?

Answer 14

It is symmetrical around the lead diagonal.

For a simple graph, the lead diagonal is all 0’s.

Question 15

What is the complement of a graph?

Answer 15

The set of edges that could be added to the graph to make it complete.

Question 16

What does the complement of a graph look like in terms of the graph’s adjacency matrix.

Answer 16

The complement switches all 0’s to ones and 1’s to 0’s, except the leading diagonal.

Question 17

What is a tree?

Answer 17

A simple-connected graph with the minimum possible number of edges.

Question 18

How many edges does a tree with n vertices have?

Answer 18

n-1 edges.

Question 19

What is a traversable graph?

Answer 19

A graph that can be drawn as a trail (without going over the same edge twice).

Question 20

What is an eulerian graph?

Answer 20

Eulerian graphs are traversable, with the trail starting and ending at the same vertex, so they are:
Connected
No vertices of odd degree

Question 21

What is a semi-eulerian graph?

Answer 21

Traversable, with the trail starting and ending at different vertices, so they are:
Connected
2 vertices of odd degree.

Question 22

What is a hamiltonian graph?

Answer 22

A graph that contains a cycle that passes through every vertex exactly once. (contains a hamiltonian cycle).
Not all the edges of the graph have to be used in the cycle.

Question 23

What is a hamiltonian cycle?

Answer 23

A cycle that passes through every vertex in the graph exactly once.

Question 24

What is a planar graph?

Answer 24

A graph that can be drawn with no edges crossing.

Question 25

What is euler’s formula true for?

Answer 25

Any connected planar graph or convex polyhedron.

Question 26

What is euler’s formula?

Answer 26

v-e+f=2
Where v is the number of vertices.
f is the number of faces
e is the number of edges

Question 27

What is important to remember when counting f, the number of faces of a graph?

Answer 27

Includes the “outside” region.

Question 28

What is kuratowski’s theorem?

Answer 28

A necessary and sufficient condition for a finite graph to be planar is that it does not contain a subgraph that is a subdivision of K5 or K3,3

Question 29

What does it mean for two graphs to be isomorphic?

Answer 29

They have the same structure, but may be drawn in different ways.