Simple graph with at least two vertices

  • Thread starter hyderman
  • Start date
  • Tags
    Graph
Therefore, in any simple graph with at least two vertices, there must be two vertices that have the same degree. This can be proven using the Pigeonhole principle.
  • #1
28
0
hello

please help by exaplaining this question in steps thank much

Show that in a simple graph with at least two vertices there must be
two vertices that have the same degree. use the Pigeonhole principle.
 
Physics news on Phys.org
  • #2
You must show your work before we can help you. Have you thought about the question? Have you tried following the hint?
 
  • #3
Have you at least drawn a picture? What happens if you try to draw a graph with exactly two vertices, each vertex having different degree?
 
  • #4
thanx for replyng i did draw a graph but i still can't understand the whole question
i know that Each vertices is connected to either 0, 1, 2, ..., n−1 other vertices but i cannot get the whole idea

please help
i
 
  • #5
so let's say you have n vertices. As you said, assume they all have different degree, then they must be,
0,1,2...n-1.

however, how can a vertex have zero degree while another vertex have n-1 degree (connecting to ALL other vertices)? contradiction.
 
  • #6
a more interesting question would be:

let there be n people in a party. Alex is in the party, and he knows that all the other people make different number of handshakes, how many handshakes does Alex make?

this classic handshake problem is closely related to this situation.
 
  • #7
please explain more in details
 
  • #8
okey can you tell me ur opinion on this thanx

Assume that the graph has n vertices. Each of those vertices is connected to either 0, 1, 2, ..., n−1 other vertices. If any of the vertices is connected to n−1 vertices, then it is connected to all the others, so there cannot be a vertex connected to 0 others. Thus, it is impossible to have a graph with n vertices where one vertex has degree 0 and another has degree n−1. Thus the vertices can have at most n−1 different degrees, but since there are n vertices, at least two must have the same degree.
 

1. What is a simple graph with at least two vertices?

A simple graph with at least two vertices is a mathematical representation of a set of objects, called vertices, connected by lines, called edges. In simple terms, it is a diagram that shows the relationship between different objects.

2. How is a simple graph different from other types of graphs?

A simple graph is different from other types of graphs, such as directed graphs or weighted graphs, because it does not have any specific direction or weight associated with its edges. This means that the edges in a simple graph do not have any specific order or value, and they are usually represented by straight lines.

3. What are the main components of a simple graph with at least two vertices?

The main components of a simple graph with at least two vertices are the vertices and edges. The vertices represent the objects or entities being studied, and the edges represent the relationships or connections between these objects. In addition, a simple graph may also have labels or weights associated with its vertices or edges, depending on the specific application.

4. Can a simple graph have loops or multiple edges?

No, a simple graph cannot have loops or multiple edges. Loops are edges that connect a vertex to itself, while multiple edges are more than one edge between two vertices. In a simple graph, each edge connects two distinct vertices, and there can only be one edge between any two vertices.

5. What are some real-world applications of simple graphs with at least two vertices?

Simple graphs with at least two vertices have various real-world applications, such as social networks, transportation networks, and computer networks. They can also be used in data analysis, such as in data visualization or clustering algorithms. Additionally, simple graphs can be used to model relationships between variables in scientific research and to study patterns and trends in various fields, such as epidemiology and economics.

Suggested for: Simple graph with at least two vertices

Back
Top