1. Prove that for any graph, the sum the degreesPv∈V deg(v) is twice the number of edges...

1. Prove that for any graph, the sum the degreesPv∈V deg(v) is twice the number of edges |E|. (By “prove” I mean write a few sentences explaining why it is true.)

2. i) At a recent math seminar, 5 mathematicians greeted each other by shaking hands. Is it possible for each mathematician to shake hands with exactly 3 other people? (No one can shake his or her own hand.) To answer the question, please rephrase the problem as a problem about graphs (is there a graph with 5 vertices ...), state your answer, and then explain why you believe your answer.
ii) Write a conjecture about a more general statement. What do you think happens if we have N mathematicians and we want each to shake the hands of K other people?

3. A very special island is inhabited only by knights and knaves. Knights always tell the truth, and knaves always lie. You meet two inhabitants: Zoey and Mel. Mel says, “At least one of us is a knave,” but Zoey says nothing. Can you determine who is a knight and who is a knave?

Expert Solution

I have explaned the 1st statement and used this statement to get the next results.

Colby Messinger answered 2 years ago

Graph Theory Prove: If G is a graph for which deg(u)+deg(v) ≥n for each uv ∈EsubG,...

Graph Theory Prove: If G is a graph for which deg(u)+deg(v) ≥n for each uv ∈EsubG, the G has a Hamiltonian cycle. (with counter examples)

Prove a connected simple graph G with 16 vertices and 117 edges is not Eulerian.

Question 1 a) Prove that if u and v are distinct vertices of a graph G,...

Question 1 a) Prove that if u and v are distinct vertices of a graph G, there exists a walk from u to v if and only if there exists a path (a walk with distinct vertices) from u to v. b) Prove that a graph is bipartite if and only if it contains no cycles of odd length. Please write legibly with step by step details. Many thanks!

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each...

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each edge labeled from the set {0,1}. Describe and analyze the worst-case time complexity of an efficient algorithm to find any cycle consisting of edges whose labels alternate 0,1.

a)Find two positive numbers such that the sum of the first number and twice the second...

a)Find two positive numbers such that the sum of the first number and twice the second number is 108 and the product is a maximum b)figure out the dimentions of a rectangular solid that has a square base of maximum volume if its surface area is 216 square inches

You are given a directed graph G(V,E) with n vertices and m edges. Let S be...

You are given a directed graph G(V,E) with n vertices and m edges. Let S be the subset of vertices in G that are able to reach some cycle in G. Design an O(n + m) time algorithm to compute the set S. You can assume that G is given to you in the adjacency-list representation.

Given a graph G = (V,E), the source-sink pair (s,t) and capacity of edges {C_e ≥...

Given a graph G = (V,E), the source-sink pair (s,t) and capacity of edges {C_e ≥ 0 | e ∈ E}, design a polynomial-time algorithm to find a set of edges S, such that for every edge e ∈ S, increasing C_e will lead to an increase of max-flow value between s and t. Show the correctness of your algorithm.

For any n ≥ 1 let Kn,n be the complete bipartite graph (V, E) where V...

For any n ≥ 1 let Kn,n be the complete bipartite graph (V, E) where V = {xi : 1 ≤ i ≤ n} ∪ {yi : 1 ≤ i ≤ n} E = {{xi , yj} : 1 ≤ i ≤ n, 1 ≤ j ≤ n} (a) Prove that Kn,n is connected for all n ≤ 1. (b) For any n ≥ 3 find two subsets of edges E 0 ⊆ E and E 00 ⊆ E such...

Prove that if G is a simple graph with |V (G)| = n even, where δ(G)...

Prove that if G is a simple graph with |V (G)| = n even, where δ(G) ≥ n 2 + 1, then G has a 3-regular spanning subgraph.

Prove or disprove: If G = (V; E) is an undirected graph where every vertex has...

Prove or disprove: If G = (V; E) is an undirected graph where every vertex has degree at least 4 and u is in V , then there are at least 64 distinct paths in G that start at u.

Question