INSTRUCTIONS TO OTA
typeset solutions
send solution as attachment
Use words to explain solutions. DO NOT RELY ONLY ON ALGEBRAIC
MANIPULATIONS/ OR SYMBOLS.
Mathematics Homework Solutions
#28048
Prove that graphs that are isomorphic have the same number of vertices and the same number of edges, and that the degree of a vertex of a graph is equal to the degree of the image of that vertex under a graph isomorphism. Also, give an example of a pair of non-isomorphic graphs that have the same number of vertices and the same number of edges.
What does it mean for two graphs to be the same? Let G and H be graphs. We say that G is isomorphic to H provided that there is a bijection f:V(G) -> V(H) so that for all a, b, in V(G) there is an edge connecting a and b (in G) if and only if there is an edge connecting f(a) and f(b) (in H). The function f is called an isomorphism of G to H.
We can think of f as renaming the vertices of G with the names of the vertices of H in a way that preserves adjacency. Less formally, isomorphic graphs have the same drawing (except for the names of the vertices).
Do the following:
(a) Prove that isomorphic graphs have the same number of vertices.
(b) Prove that if f:V(G) -> V(H) is an isomorphism of graphs G and H and if v is an element of V(G), then the degree of v in G equals the degree of f(v) in H.
(c) Prove that isomorphic graphs have the same number of edges.
(d) Give an example of two non-isomorphic graphs that have the same number of vertices and the same number of edges.
Step-by-step proofs of parts (a) through (c) are given. For (d), an example of a pair of non-isomorphic graphs with the same number of vertices and the same number of edges is provided in an attached .doc file.
What is this?
By OTA - Overall OTA Rating
Georgia Martin, PhD - 4.8/5
Purchase Cost Now
$2.19 CAD (was ~$3.99)
Included in Download
- Plain text response
- Attached file(s):
- GraphIsomorphism-Solution.doc
Why you can trust BrainMass.com
- Your Information is Secure
- Best Online Academic Help Service
- Students find real academic Success
- Self-complementary graph - 1.10 Let G be a self-complementary graph of order n, where n=1(mod 4) Prove that G contains at least one vertex of degree (n-1)/2 (hint: Prove the stronger result that G contains an odd number of ve ...
- Discrete Math - Please help me with this one! 1. Let G be an undirected graph with n vertices. If G is isomorphic to its own compliment , how many edges must G have?
- Geometry - Would like more details and explanations as to how the attached graph is solved. Create a graph with four odd vertices. See attached file for full problem description.
- Planar graph - I need to show that if G is a planar graph, then G must have a vertex of degree at most 5.
- Graphs and Digraphs - 1.) Give an example of a planar graph that contains no vertex of degree less than 5 2.) Show that every planar graph of order n≥4 has at least four vertices of degree less than or equal to 5. ...
