Discrete Shortcut ways to do things

Question 1

Check your degrees/order/valency are correct

Answer 1

Add up degrees and if sum is even then you’re good

Question 2

How to check if graph is isomorphic

Answer 2

• Need same number vertices
• Need same number of edges
• Check degree of each vertex
• Match up vertices: label each vertex with unique degrees first then match up and label the others
• Check that the edges are the same
• Isomorphic

Question 3

How to check if graph is Hamiltonian (sequence of edges with no repeated edges or vertices that visits every vertex once then returns to start vertex)

Answer 3

Number of vertices = number of edges

n-1 edges needed to connect all vertices then one extra edge needed to return to start

Question 4

Which graph can you never find Hamiltonian cycle (sequence of edges with no repeated vertices or edges that visits every vertex once then returns to start vertex) for?

Answer 4

Tree (connected graph with no cycles- sequences of edges not repeating vertices or edges that can return back to start vertex)
Disconnected graph (where it's split up)

Question 5

Can you explain why the complete graph K4 has 3 Hamiltonian cycles?

Answer 5

Starting vertex is A
then 3 choices for second vertex
then 2 choices for third vertex (2 left to visit)
then 1 choice for fourth vertex
3x2x1=6
Each cycle listed in 2 orders (forwards and backwards)