/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Problem 29 Show that if \(m\) and \(n\) are... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 10: Problem 29

Show that if \(m\) and \(n\) are even positive integers, the crossing number of \(K_{m, n}\) is less than or equal to \(m n(m-2)\) \((n-2) / 16 .[\text { Hint: Place } m \text { vertices along the } x \text { -axis so }\) that they are equally spaced and symmetric about the origin and place \(n\) vertices along the \(y\) -axis so that they are equally spaced and symmetric about the origin. Now connect each of the \(m\) vertices on the \(x\) -axis to each of the vertices on the \(y\) -axis and count the crossings.

Short Answer

Expert verified
The crossing number is at most \(\frac{mn(m-2)(n-2)}{16}\).

Step by step solution

01

Understand the problem

Given even positive integers \( m \) and \( n \), where \( K_{m,n} \) is a complete bipartite graph, the challenge is to show that the crossing number (minimum number of edge crossings when the graph is drawn in a plane) is less than or equal to \(\frac{mn(m-2)(n-2)}{16}\).
02

Position the vertices

Place \( m \) vertices evenly spaced along the \( x \)-axis, symmetric about the origin. Similarly, place \( n \) vertices evenly spaced along the \( y \)-axis, symmetric about the origin.
03

Connect the vertices

Draw edges connecting each vertex on the \( x \)-axis to each vertex on the \( y \)-axis. Each of the \( m \) vertices on the \( x \)-axis will be connected to each of the \( n \) vertices on the \( y \)-axis, producing \( mn \) edges.
04

Count the crossings

When edges are drawn between vertices on the axis, two edges will intersect if and only if their endpoints alternate. For each pair of edges \((a, b)\) and \((c, d)\) where \(a\) is on the \( x \)-axis and \(b\) is on the \( y \)-axis, \(c\) is on the \( x \)-axis and \(d\) is on the \( y \)-axis, and \(a < c\) and \(b > d\), there will be an intersection. Let鈥檚 consider calculating the total number of such pairs.
05

Calculate combinations of crossings

Each vertex on the \( x \)-axis corresponds with \( m-2 \) other vertices. Similarly, each vertex on the \( y \)-axis corresponds with \( n-2 \) other vertices. Therefore, the maximum number of crossings is given by \((m-2)(n-2)\) combinations.
06

Apply the formula

Form the expression \(\frac{mn}{16}\) and combine it with the number of crossing pairs found to get the final result. Thus the maximum number of crossings is \(\frac{mn(m-2)(n-2)}{16}\).

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

graph theory
Graph theory is a significant area of mathematics and computer science focusing on the study of graphs. A graph consists of vertices (sometimes called nodes) and edges (lines that connect them). Graph theory helps in understanding complex networks and solving problems related to them.

In real-world applications:
  • Road networks use graph theory to find the shortest paths.
  • Social networks apply graph theory to analyze connections between people.
  • Biologists use graph theory to model and understand biological processes.
In graph theory, different types of graphs exist, such as simple graphs, directed graphs, and bipartite graphs. Each type has unique properties and uses.
complete bipartite graph
A complete bipartite graph is a special type of bipartite graph where every vertex from one partition is connected to every vertex in the other partition. It is denoted as \(K_{m,n}\), where m and n are the sizes of the two partitions.

In a bipartite graph:
  • Vertices are divided into two disjoint sets.
  • No two vertices within the same set are adjacent.
In a complete bipartite graph:
  • Every vertex in the first set connects to every vertex in the second set.
  • This forms \(m \times n\) edges in total.
For example, \(K_{3,4}\) has two sets with 3 and 4 vertices. Each vertex from the set of 3 connects to each vertex in the set of 4, creating 12 edges.
crossing number
The crossing number of a graph is the minimum number of edge crossings in a drawing of the graph on a plane. For a complete bipartite graph, calculating this requires specific strategies due to the number of vertices and edges.

To find the crossing number of \(K_{m,n}\):
  • Position m vertices along the x-axis, spaced symmetrically.
  • Position n vertices along the y-axis, spaced symmetrically.
  • Draw edges connecting each vertex on the x-axis to every vertex on the y-axis.
The challenge is to count the crossings. For vertices placed symmetrically around the origin:
  • Edges will cross only if their endpoints alternate, for instance, when vertices connect as (a,b) and (c,d) such that a < c and b > d.
Calculate the intersections using combinations of vertices, arriving at the formula \frac{mn(m-2)(n-2)}{16}\, which provides an upper bound for the crossing number. This formula helps in understanding how vertex placement affects edge crossings in a graph.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Show that a simple graph \(G\) with \(n\) vertices is connected if it has more than \((n-1)(n-2) / 2\) edges.

Show that if \(u\) and \(v\) are nonadjacent vertices in a graph \(G\) with \(n\) vertices and \(\operatorname{deg}(u)+\operatorname{deg}(v) \geq n,\) then \(G\) has a Hamilton circuit if and only if \(G+\\{u, v\\}\) has a Hamilton circuit.

Suppose that a planar graph has \(k\) connected components, \(e\) edges, and \(v\) vertices. Also suppose that the plane is divided into \(r\) regions by a planar representation of the graph. Find a formula for \(r\) in terms of \(e, v,\) and \(k .\)

How many nonisomorphic directed simple graphs are there with \(n\) vertices, when \(n\) is $$\begin{array}{llll}{\text { a) } 2 ?} & {\text { b) } 3 ?} & {\text { c) } 4 ?}\end{array}$$

The parts of this exercise outline a proof of Ore's theorem. Suppose that \(G\) is a simple graph with \(n\) vertices, \(n \geq 3,\) and \(\operatorname{deg}(x)+\operatorname{deg}(y) \geq n\) whenever \(x\) and \(y\) are non-adjacent vertices in \(G .\) Ore's theorem states that under these conditions, \(G\) has a Hamilton circuit. a) Show that if \(G\) does not have a Hamilton circuit, then there exists another graph \(H\) with the same vertices as \(G,\) which can be constructed by adding edges to \(G,\) such that the addition of a single edge would produce a Hamilton circuit in \(H .[\text {Hint} : \text { Add as many edges as }\) possible at each successive vertex of \(G\) without producing a Hamilton circuit.] b) Show that there is a Hamilton path in \(H\) c) Let \(v_{1}, v_{2}, \ldots, v_{n}\) be a Hamilton path in \(H .\) Show that \(\operatorname{deg}\left(v_{1}\right)+\operatorname{deg}\left(v_{n}\right) \geq n\) and that there are at most \(\operatorname{deg}\left(v_{1}\right)\) vertices not adjacent to \(v_{n}\) (including \(v_{n}\) itself). d) Let \(S\) be the set of vertices preceding each vertex adjacent to \(v_{1}\) in the Hamilton path. Show that \(S\) contains \(\operatorname{deg}\left(v_{1}\right)\) vertices and \(v_{n} \notin S .\) e) Show that \(S\) contains a vertex \(v_{k}\) that is adjacent to \(v_{n}\) implying that there are edges connecting \(v_{1}\) and \(v_{k+1}\) and \(v_{k}\) and \(v_{n} .\) f) Show that part (e) implies that \(v_{1}, v_{2}, \ldots, v_{k-1}\) \(v_{k}, v_{n}, v_{n-1}, \ldots, v_{k+1}, v_{1}\) is a Hamilton circuit in \(G\) . Conclude from this contradiction that Ore's theorem holds.
See all solutions

Recommended explanations on Math Textbooks

Discrete Mathematics

Read Explanation

Decision Maths

Read Explanation

Geometry

Read Explanation

Mechanics Maths

Read Explanation

Statistics

Read Explanation

Logic and Functions

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.