0
votes
0answers
35 views

A planar graph has either 2 faces or 2 vertices of degree less than 3

Practicing for an upcoming test, I stumbled upon this question: A planar graph with at least three vertices has either 2 faces of length at most 3, or 2 vertices of degree at most 3. Which is a ...
4
votes
1answer
257 views

Issue concerning enumerating vertices in a prism (number of two adjacent vertices can only differ by a certain amount)

There are 100 vertices in a prism with a 50-gon as its base. Those vertices are assigned integers 1 to 100 (inclusive) in a random order. Each number can only be assigned once. The objective is to ...
2
votes
3answers
187 views

Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information: A graph has 17 vertices and 129 edges. ...
1
vote
1answer
66 views

pigeonhole principle related problem

I'm given the problem: In a tournament which 18 teams participate, a team being matched with another in a round don’t match again in the follwoing (later) rounds. After 8 rounds prove that there are 3 ...
1
vote
3answers
237 views

Pigeonhole Principle Question - Group of 6 people, do 3 either know each other or not?

Prove that in any group of 6 people there are always at least 3 people who either all know one-another or all are strangers to one-another. Hint: Use the pigeonhole principle. I don't see how this ...
1
vote
2answers
82 views

90 people with ten friends in the group. Prove its possible to have each person invite 3 people such that each knows at least two others

A high school has 90 alumni, each of whom has ten friends among the other alumni. Prove that each alumni can invite three people for lunch so that each of the four people at the lunch table will know ...
1
vote
1answer
53 views

Midpoints joining integers on a plane lattice

How can you prove that if five nodes of a plane lattice are chosen at random then, the midpoint of the segment between the two points is a lattice point.
2
votes
1answer
418 views

Pigeonhole Principle on Graphs

I just have a last minute question for my combinatorics final (which is in one hour!!). My prof particularly told me to study the following question and I'm pretty sure it involves the pigeonhole ...