Deck 10: A: Graphs

Question 1

fill in the blanks.
There are 0's and 1's in the adjacency matrix for

Answer 1

Question 2

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 2

Question 3

fill in the blanks.
The adjacency matrix for has 1's and 0's.

Answer 3

n(n − 1), n

Question 4

fill in the blanks.
has edges and vertices.

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 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 7

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?

Question 8

fill in the blanks.
The length of the longest simple circuit in K4,10 is .

Question 9

fill in the blanks.
The adjacency matrix for has columns.

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

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 12

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 13

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 14

fill in the blanks.
The length of the longest simple circuit in is .

Question 15

fill in the blanks.
The length of the longest simple circuit in is .

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

fill in the blanks.

Question 18

fill in the blanks.
has edges and vertices.

Question 19

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 20

fill in the blanks.
List all positive integers n such that is bipartite .

Question 21

fill in the blanks.
List all positive integers n such that has a Hamilton circuit.

Question 22

fill in the blanks.
There are non-isomorphic simple undirected graphs with 5 vertices and 3 edges.

Question 23

fill in the blanks.
List all positive integers m and n such that has a Hamilton path but no Hamilton circuit.

Question 24

fill in the blanks.
List all positive integers n such that has an Euler circuit.

Question 25

fill in the blanks.
There are non-isomorphic simple digraphs with 3 vertices and 2 edges.

Question 26

fill in the blanks.
List all positive integers n such that has an Euler circuit.

Question 27

fill in the blanks.
The incidence matrix for Q5 has rows and columns.

Question 28

fill in the blanks.
List all positive integers n such that has a Hamilton circuit.

Question 29

fill in the blanks.
Every Hamilton circuit for has length .

Question 30

fill in the blanks.
The largest value of n for which is planar is .

Question 31

fill in the blanks.
The largest value of n for which is planar is .

Question 32

fill in the blanks.
List all positive integers m and n such that has a Hamilton circuit.

Question 33

fill in the blanks.
List all positive integers n such that has an Euler circuit.

Question 34

fill in the blanks.
List all positive integers n such that has a Hamilton circuit.

Question 35

fill in the blanks.
The incidence matrix for has rows and columns.

Question 36

fill in the blanks.
Every Euler circuit for has length .

Question 37

fill in the blanks.
List all the positive integers n such that is planar.

Question 38

fill in the blanks.
List all positive integers n such that has a Hamilton circuit but no Euler circuit.

Question 39

fill in the blanks.
There are non-isomorphic simple graphs with 3 vertices.

Question 40

fill in the blanks.
The adjacency matrix for has entries.

Question 41

Question 42

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

Question 43

fill in the blanks.
The vertex-chromatic number for = .

Question 44

fill in the blanks.
The vertex-chromatic number for = .

Question 45

Find the strongly connected components of the graph.

Question 46

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

Question 47

Find the strongly connected components of the graph.

Question 48

Question 49

fill in the blanks.
The Euler formula for planar connected graphs states that .

Question 50

fill in the blanks.
The vertex-chromatic number for = .

Question 51

fill in the blanks.
If G is a connected graph with 12 regions and 20 edges, then G has vertices.

Question 52

fill in the blanks.
If G is a planar connected graph with 20 vertices, each of degree 3, then G has regions.

Question 53

fill in the blanks.
The edge-chromatic number for = .

Question 54

fill in the blanks.
The region-chromatic number for = .

Question 55

For each of the graphs in 56-58 find

Question 56

fill in the blanks.
If a regular graph G has 10 vertices and 45 edges, then each vertex of G has degree .

Question 57

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 58

fill in the blanks.
The vertex-chromatic number for = .

Question 59

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

Question 60

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

Question 61

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

Question 62

either give an example or prove that there are none.
A planar graph with 8 vertices, 12 edges, and 6 regions.

Question 63

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.

Question 64

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 65

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

Question 66

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 67

either give an example or prove that there are none.
A planar graph with 7 vertices, 9 edges, and 5 regions.

Question 68

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

Question 69

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

Question 70

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 71

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

Question 72

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 73

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

Question 74

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

Question 75

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

Question 76

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 77

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

Question 78

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

Question 79

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

Question 80

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.