Purchase Solution

Graphs, Vertices and Cycle Length

Not what you're looking for?

Ask Custom Question

A nontrivial graph G is called prime if G = G_1 x G_2 implies that G_1 or G_2 is trivial. Show that if a connected graph G has a vertex which is not in a cycle of length four, then G is prime.

where "x" is the cartesian product

Purchase this Solution
Solution Summary

Graphs, Vertices and Cycle Length are investigated. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.

Solution Preview

Please see the attached file for the complete solution.
Thanks for using BrainMass.

Prob 75 : Show that if a connected graph G has a vertex which is not in a cycle of length four, then G is prime.

Proof : Let G be a graph having no cycle of length ...

Purchase this Solution
Free BrainMass Quizzes
Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Probability Quiz

Some questions on probability

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

View More Free Quizzes
Related BrainMass Solutions

  • Complete Graphs and Cycles; Undirected & Spanning Trees and Reverse Polish Notation

    96674 Complete Graphs and Cycles; Undirected & Spanning Trees and Reverse Polish Notation Consider a comple graph G, n ≥ 3. Find the number of cycles in G of length n. How many cycles in a complete graph with 5 vertices?

  • Hamiltonian proofs

    (b) An n-cube Qn is such a graph G that its vertex is a binary code of length n and two vertices has an edge if they have exactly one bit difference.

  • Undergrad Topology Vertice Proofs

    (v :vertices and e : edges) For the proof we need to introduce a class of special graphs.

  • Eulerian Graph

    We have examples of Eulerian graphs with N_{RE} = 0, 1, and 2 randomly Eulerian vertices in posting 145698, so we only need to prove that if a graph has N_{RE} > 2 randomly Eulerian vertices then all its vertices are randomly Eulerian.

  • Forests and Eulerian Graphs

    145701 Forests and Eulerian Graphs Let F be a forest. Add a vertex x to F and join x to each vertex of odd degree in F.

  • Graphs, Digraphs, Trees and Forests

    Now consider the induced subgraph on the vertices. This graph will have all the edges of the cycle we are considering. Clearly all the vertices in this graph are on the cycle and have degree at least 2. There fore we have proved claim -- (2).

  • Simple Circuitts

    So, if T is a tree with 999 vertices, then T has 998 edges There are two questions: The length of the longest simple circuit, and how many edges are in a tree with 999 vertices

  • Randomly Eulerian Graphs

    As all vertices are of even degree in an Eulerian graph, T must terminate at V. Therefore all the vertices of G-T, the remnant of G after removal of T, have an even degree and so G-T is an Eulerian graph itself and so has at least one cycle.

  • Subgraphs

    This shows how to characterize graphs that are connected and induced.

View More Related Solutions