Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Graphs

Graphs

1.[1p]

A simple graph has degrees 6,5,4,4,3,2,2. How many edges does it have?

CorrectNot quite: 13

2.[1p]

Every vertex of a graph has degree 3, and the graph has 24 edges. How many vertices does it have?

CorrectNot quite: 16

3.[3p]

Which of these lists are the degrees of some simple graph?

Select all that apply

Correct
The answer is: $3, 3, 3, 3$, $2, 2, 2, 2, 2$, $4, 3, 3, 2, 2$
Correct
The answer is: $3, 3, 3, 3$, $2, 2, 2, 2, 2$, $4, 3, 3, 2, 2$
Correct
The answer is: $3, 3, 3, 3$, $2, 2, 2, 2, 2$, $4, 3, 3, 2, 2$

4.[1p]

Which of these is not an isomorphism invariant?

The answer is: Whether the vertex named $1$ has degree $3$
The answer is: Whether the vertex named $1$ has degree $3$
The answer is: Whether the vertex named $1$ has degree $3$
Correct

5.[2p]

A graph on the vertices 1,2,…,13 has edges {1,4},{4,7},{2,5},{5,8},{8,2},{3,6},{9,10},{10,3},{11,12}. How many connected components does it have?

CorrectNot quite: 5

6.[2p]

A town's four land masses are joined by six bridges, the land is connected, and the numbers of bridges at the four land masses are 4,3,3,2. Which statement is true?

Correct
The answer is: A walk crossing every bridge exactly once exists, and it must start at one of the two land masses with $3$ bridges and end at the other
The answer is: A walk crossing every bridge exactly once exists, and it must start at one of the two land masses with $3$ bridges and end at the other
The answer is: A walk crossing every bridge exactly once exists, and it must start at one of the two land masses with $3$ bridges and end at the other

7.[2p]

In Euler's Königsberg the land masses had 5,3,3,3 bridges. What is the fewest new bridges that could be built so that a closed walk crossing every bridge exactly once becomes possible?

CorrectNot quite: 2

8.[2p]

Dirac's theorem guarantees a Hamilton cycle in a simple graph on 11 vertices provided every vertex has degree at least what whole number?

CorrectNot quite: 6

9.[1p]

Match each condition on a graph to what it guarantees or implies.

  • Connected, every degree even

  • Connected, exactly two odd degrees

  • Four vertices of odd degree

  • Simple, at least three vertices, every degree at least half the number of vertices

  • points

  • tags

  • an Euler circuit

  • 2

  • euler-theorem, hamilton-cycles

  • an Euler trail between the two odd vertices

  • no Euler trail at all

  • a Hamilton cycle

Show the answer

Connected, every degree even: an Euler circuit Connected, exactly two odd degrees: an Euler trail between the two odd vertices Four vertices of odd degree: no Euler trail at all Simple, at least three vertices, every degree at least half the number of vertices: a Hamilton cycle

points: 2 tags: euler-theorem, hamilton-cycles