Math Help - Graph Theory

[79wjd]

I need help going over a past exam and would appreciate any help I can get from anyone who has taken any proof-based Graph theory courses. 

 

If anyone thinks they know enough Graph theory to help, please respond/PM me. 

 

@Dash Lambda I know this isn't the usual diffeq question, but do you by any chance know someone who has taken a graph theory course?

[Dash Lambda]

I've done a discrete math course, graph theory is a big topic in that. What do you need help with?

[79wjd]

15 minutes ago, Dash Lambda said:

I've done a discrete math course, graph theory is a big topic in that. What do you need help with?

I wanted to go over this test and figure out why I got wrong what I got wrong, and if there are any points that I shouldn't have lost because when I compared my answers to similar class/homework problems they seem close enough. (specifically questions 6,7,8 I feel like I deserved like an extra 20 points or so)

 

Normally I would just go see the professor, but I'm taking off the semester for medical reasons, so I won't be able to see him until the fall. 

 

dfg.pdf

[Dash Lambda]

On 4/19/2017 at 8:30 AM, djdwosk97 said:

-snip-

Sorry for the wait, busy week mixed with the need for a bit more work than usual (the graph theory unit I had was mostly just introductory)

made this take a while.

 

It looks like, for the proofs, you’re getting marked down mostly for either leaving out properties that the question specifies or not giving rigorous relationships between properties.

 

1: Ignore any given theorems, the answer concerns only observation.

 

2: -(i) It looks like your proof is mostly there, but not complete. You need to show explicitly that it cannot have 7 faces.
-(ii) The question specifies a graph with k components, therefore it is not necessarily a connected graph. You must account for that.
-I’d use Kuratowski’s theorem for 3 and 4.

 

5: -(ii) The relationship here is nonlinear. Think combinations.
-(iii) Multiplying the number of spanning trees by 3/(n+1) implies that there are fewer spanning trees for the modified graphs for n>2, which is not the case.
-(iv) This relationship is also nonlinear.

 

6: -(iii) That is the edge form. It can’t directly address the minimum vertex cover.
-(ii) The relationships between the individual properties must be justified. The usual way is to add two nodes to a bipartite graph, each connecting to every edge in their respective halves of the graph (but not each other), then work off of the paths between those two points.

 

7: Oh, I do hate questions that require such roundabout methods…
I would prove it like this: Given the graph K_n,n, it is known that each node is of degree n and there are n distinct perfect matchings, where each perfect matching contributes exactly once to the degree of each node. It follows that the adjacency matrix of each perfect matching contains exactly one entry per row and column, and is therefore a permutation matrix. The adjacency matrix of K_n,n is therefore the sum of n permutation matrices, and as each node is of degree n, the sum of each row and column is n.
If the number of matchings does not equal the degree of each node, then not every matching is a perfect matching, and therefore does not correspond to a permutation matrix.
(I’m not sure how tight your professor wants your focus to be when a number is specified, but either way this proof applies to 10.)

 

8: I notice a couple errors:
-First one I’m not actually sure if it’s an error or part of your proof by contradiction, but the inequality for Tutte’s theorem is reversed.
-G is k-1 edge-connected, as there does not exist a set of k-2 edges that disconnect the graph.
-Each connected component must have at least k-1 edges between it and S, else there is a set of k-2 edges which disconnect the graph.

 

10: K_1,1 is actually not Hamiltonian, though the minimum degree as per the question for a graph of order 2 is 2, so the graph in question is.
To prove that it’s sharp, you just need to show that you can construct a disconnected graph for the relevant n’s if the minimum degree is n/4.
 

I obviously don't know as much as I'd hoped, but I do hope this helps.