Network Stuff

Question 1

How can you test if two graphs are isomorphic?

Answer 1

1) Count nodes
2) Count edges
3) Check degrees

if one doesn’t match you can ignore the rest, the graphs are not isomorphic

Question 2

Draw a K5 graph (complete graph with 5 vertices)?

Answer 2

It looks like a pentagon with a star in the middle (one point at each corner where the nodes are)

Question 3

What is stated by Euler’s handshaking lemma?

Answer 3

In any undirected graph, the sum of the degrees of the verticies is equal to 2*the number of edges

Question 4

What is one way to check for a Hamiltonian cycle?

Answer 4

Count the edges. To connect n nodes takes (n-1) edges and returning to the beginning takes one extra so a Hamiltonian cycle must have the same number of edges and verticies

Question 5

What is the equation for number of distinct cycles for Kn graph?

Answer 5

(n-1)! / 2

Question 6

what is the equation for sum of the order of allnverticies of a Kn graph?

Answer 6

n(n-1)

Question 7

What is the equation for edge count of a Kn graph?

Answer 7

n(n-1) / 2