Deck 10: Graphs

Question 1

In questions fill in the blanks.1113:1156

Answer 1

Question 2

Many supermarkets use loyalty or discount cards to keep track of who buys which items. How can graphs
be used to model this relationship? Should the edges be directed or undirected? Should multiple edges be
allowed? Should loops be allowed? Does this graph have any special properties?

Answer 2

Use vertices to represent the customers and the items stocked. An edge connecting a customer u to an item
v is drawn if u buys v. Multiple edges are allowed, since customers can buy several items of the same kind.
Note that the graph is bipartite.

Question 3

Construct a call graph for five friends Alice, Bob, Charlie, Diane and Evan, if there were three calls from Alice
to Bob, two calls from Alice to Diane, five calls from Alice to Evan, one call from Bob to Alice, three calls
from Charlie to Alice, one call from Charlie to Evan, one call from Diane to Charlie, and one call from Evan
to Diane.

Answer 3

Question 4

In questions fill in the blanks.1113:1156
The length of the longest simple circuit in .

Question 5

for each graph give an ordered pair description (vertex set and edge set) and an adjacency
matrix, and draw a picture of the graph.

Question 6

In questions fill in the blanks.1113:1156
The adjacency matrix for

Question 7

In questions fill in the blanks.1113:1156
The length of the longest simple circuit in .

Question 8

In the group stage of the 2011 women's soccer world cup the USA beat North Korea, Sweden beat Columbia,
the USA beat Columbia, Sweden beat North Korea, Sweden beat the USA, and the game between Columbia
and North Korea ended in a tie. Model this outcome using a directed segment from A to B if A beat B, and
an undirected segment if the game ended in a tie.

Question 9

for each graph give an ordered pair description (vertex set and edge set) and an adjacency
matrix, and draw a picture of the graph.

Question 10

for each graph give an ordered pair description (vertex set and edge set) and an adjacency
matrix, and draw a picture of the graph.

Question 11

In questions fill in the blanks.1113:1156
List all positive integers .

Question 12

During the construction of a home there are certain tasks that have to be completed before another one can
commence, e.g., the roof has to be installed before the work on electrical wiring or plumbing can begin. How
can a graph be used to model the different tasks during the construction? Should the edges be directed or
undirected? Looking at the graph model, how can we find tasks that can be done at any time and how can
we find tasks that do not have to be completed before other tasks can begin?

Question 13

In questions fill in the blanks.1113:1156
The adjacency matrix for

Question 14

In questions fill in the blanks.1113:1156
.

Question 15

In questions fill in the blanks.1113:1156

Question 16

for each graph give an ordered pair description (vertex set and edge set) and an adjacency
matrix, and draw a picture of the graph.

Question 17

Explain how graphs can be used to model the spread of a contagious disease. Should the edges be directed or
undirected? Should multiple edges be allowed? Should loops be allowed?

Question 18

In questions fill in the blanks.1113:1156

Question 19

In questions fill in the blanks.1113:1156

Question 20

for each graph give an ordered pair description (vertex set and edge set) and an adjacency
matrix, and draw a picture of the graph.
K6.

Question 21

In questions fill in the blanks.1113:1156

Question 22

In questions fill in the blanks.1113:1156
There are non-isomorphic simple digraphs with 3 vertices and 2 edges.

Question 23

In questions fill in the blanks.1113:1156

Question 24

In questions fill in the blanks.1113:1156

Question 25

In questions fill in the blanks.1113:1156

Question 26

In questions fill in the blanks.1113:1156

Question 27

In questions fill in the blanks.1113:1156
List all positive integers n such that

Question 28

In questions fill in the blanks.1113:1156
The adjacency matrix for

Question 29

In questions fill in the blanks.1113:1156

Question 30

In questions fill in the blanks.1113:1156
The incidence matrix for

Question 31

In questions fill in the blanks.1113:1156
There are non-isomorphic simple graphs with 3 vertices.

Question 32

In questions fill in the blanks.1113:1156

Question 33

In questions fill in the blanks.1113:1156
The incidence matrix for

Question 34

In questions fill in the blanks.1113:1156

Question 35

In questions fill in the blanks.1113:1156

Question 36

In questions fill in the blanks.1113:1156
There are 0's and 1's in the adjacency matrix for Cn.

Question 37

In questions fill in the blanks.1113:1156

Question 38

In questions fill in the blanks.1113:1156

Question 39

In questions fill in the blanks.1113:1156

Question 40

In questions fill in the blanks.1113:1156
There are non-isomorphic simple undirected graphs with 5 vertices and 3 edges.

Question 41

In questions fill in the blanks.1113:1156
Determine whether the graph is strongly connected, and if not, whether it is weakly connected.

Question 42

Determine whether the graph is strongly connected, and if not, whether it is weakly connected.

Question 43

In questions fill in the blanks.1113:1156

Question 44

In questions fill in the blanks.1113:1156

Question 45

Find the strongly connected components of the graph.

Question 46

In questions fill in the blanks.1113:1156

Question 47

In questions fill in the blanks.1113:1156

Question 48

Question 49

In questions fill in the blanks.1113:1156

Question 50

In questions fill in the blanks.1113:1156

Question 51

In questions fill in the blanks.1113:1156

Question 52

In questions fill in the blanks.1113:1156

Question 53

In questions either give an example or prove that there are none.

Question 54

In questions fill in the blanks.1113:1156

Question 55

Find the strongly connected components of the graph.

Question 56

In questions fill in the blanks.1113:1156

Question 57

Question 58

In questions fill in the blanks.1113:1156

Question 59

In questions either give an example or prove that there are none.
A simple graph with 8 vertices, whose degrees are 0, 1, 2, 3, 4, 5, 6, 7.

Question 60

Question 61

In questions either give an example or prove that there are none.
A graph with 9 vertices with edge-chromatic number equal to 2.

Question 62

In questions either give an example or prove that there are none.
A graph with 6 vertices that has an Euler circuit but no Hamilton circuit.

Question 63

In questions either give an example or prove that there are none.
A connected simple planar graph with 5 regions and 8 vertices, each of degree 3.

Question 64

In questions either give an example or prove that there are none.
A simple digraph with indegrees 1, 1, 1 and outdegrees 1, 1, 1.

Question 65

In questions either give an example or prove that there are none.
A simple digraph with indegrees 0, 1, 2 and outdegrees 0, 1, 2.

Question 66

In questions either give an example or prove that there are none.
A simple digraph with indegrees 0, 1, 1, 2 and outdegrees 0, 1, 1, 1.

Question 67

In questions either give an example or prove that there are none.
A graph with 7 vertices that has a Hamilton circuit but no Euler circuit.

Question 68

In questions either give an example or prove that there are none.
A graph with a Hamilton path but no Hamilton circuit.

Question 69

In questions either give an example or prove that there are none.
A simple graph with 6 vertices and 16 edges.

Question 70

In questions either give an example or prove that there are none.
A graph with region-chromatic number equal to 6.

Question 71

In questions either give an example or prove that there are none.
A simple digraph with indegrees 0, 1, 2, 2 and outdegrees 0, 1, 1, 3.

Question 72

In questions either give an example or prove that there are none.
A simple graph with degrees 1, 2, 2, 3.

Question 73

In questions either give an example or prove that there are none.
A simple graph with degrees 1, 1, 2, 4.

Question 74

In questions either give an example or prove that there are none.
A simple digraph with indegrees: 0, 1, 2, 2, 3, 4 and outdegrees: 1, 1, 2, 2, 3, 4.

Question 75

In questions either give an example or prove that there are none.
A graph with a Hamilton circuit but no Hamilton path.

Question 76

In questions either give an example or prove that there are none.
A planar graph with 10 vertices.

Question 77

In questions either give an example or prove that there are none.
A graph with 4 vertices that is not planar.

Question 78

In questions either give an example or prove that there are none.
A graph with vertex-chromatic number equal to 6.

Question 79

In questions either give an example or prove that there are none.
A simple graph with degrees 2, 3, 4, 4, 4.

Question 80

In questions either give an example or prove that there are none.
A simple digraph with indegrees 0, 1, 2, 4, 5 and outdegrees 0, 3, 3, 3, 3.