People at the party and counting friends

I'll try to find that graph when I get back from work. I'll make a post, don't worry.I'll try to find that graph when I get back from work. I'll make a post, don't worry.I've done some research and I found out that there are exactly 11 regular graphs with degree 3 which can be upgraded to degree 4. These are the only possible graphs made of 6 vertices. I tried every one of them multiple times but I didn't succeed. I also tried to make some connections between these graphs and directed graphs where every vertex has exactly 1 in-degree and 1 out-degree but I haven't found any connection.Yes, I'm asking for all possible values of n
  • #1
2
0
Hi
1. Homework Statement

On the party came n people. In the beginning all of them have had exactly 3 friends among party members. During party some people made new friends and at the end of the party everyone had exactly 4 friends among party members. Set all numbers n for which the following statement is true. (if person A knows person B, then person B knows person A)

Homework Equations

The Attempt at a Solution


I found only some law that says -> "In any party of six people either at least three of them are (pairwise) mutual strangers or at least three of them are (pairwise) mutual acquaintances.", but I don't have an idea how to use that to solve this. Making combinations of possible cases i feel like it has to be n > 6 but i have no clue how to prove that.

Thanks in advance for all tips,
mfg
 
Physics news on Phys.org
  • #2
Archinald said:
for which the following statement is true.
What following statement?
 
  • #3
Archinald said:
On the party came n people. In the beginning all of them have had exactly 3 friends among party members. During party some people made new friends and at the end of the party everyone had exactly 4 friends among party members. Set all numbers n for which the following statement is true. (if person A knows person B, then person B knows person A)

Pehaps the question is being translated from a different language or culture. Can we phrase it like this ?:

Assume n people attend a party. Initially, each person at the party recognizes exactly 3 other attendees. At the end of the party, each person recognizes exactly 4 attendees. List the possible values of n for which the following statement can be true at the end of the party: Each person who recognizes another attendee is recognized by that attendee.

I'm using 'recognize" as non-symmetric relation. For example, you might recognize a famous actor at a party, but the actor might not recognize you.
 
  • #4
Stephen Tashi said:
Pehaps the question is being translated from a different language or culture. Can we phrase it like this ?:

Assume n people attend a party. Initially, each person at the party recognizes exactly 3 other attendees. At the end of the party, each person recognizes exactly 4 attendees. List the possible values of n for which the following statement can be true at the end of the party: Each person who recognizes another attendee is recognized by that attendee.

I'm using 'recognize" as non-symmetric relation. For example, you might recognize a famous actor at a party, but the actor might not recognize you.

Yes, that's right translation, but there are only symmetrical relations in question - if first person knows or recognizes second person then second person recognizes first person as well.

EDIT - I just read again your post and realized you wrote about symmetric rule in last sentence. It's pretty late in my time zone ; ) anyway thanks for replying.
 
  • #5
Archinald said:
there are only symmetrical relations in question - if first person knows or recognizes second person then second person recognizes first person as well.

Then should the last sentence of the problem say:
"List the possible values of n for which the following statement can be true at the end of the party: Each person recognizes every other person"
?
 
  • #6
The way I read the question,
Archinald said:
(if person A knows person B, then person B knows person A)
specified that the 'friends' relation was symmetric throughout. Archinald's subsequent posts appear to confirm that. That leaves unanswered my question as to what the 'following statement' is.
Archinald, is it asking for what n the preceding statements are possible?
 
  • #7
An undirected graph has n vertices. Each vertex has edges that connect it to exactly 3 other vertices. Edges are added to the graph so that each vertex has edges that connect it to exactly 4 other vertices. When this is done, all the vertices of the graph are connected to each other by edges. What are the possible values for n ?
 
  • #8
Stephen, I'm with you until this part:
Stephen Tashi said:
When this is done, all the vertices of the graph are connected to each other by edges.
I don't see where you get that from in the OP posts.
You can delete that sentence from your post and still have a worthwhile puzzle.
 
  • #9
I can make it work for n=6. Just don't start with K3,3. Show us the before and after graphs :-)

If we add one friendship, that increases the friend count for 2 people from 3 to 4...
 
  • #10
Joffan said:
I can make it work for n=6. Just don't start with K3,3.
Quite so - there are only two regular degree 3 graphs on 6 vertices. K3,3 cannot be extended to regular degree 4 but the other can.
Joffan said:
Show us the before and after graphs
Are you asking Archinald to find the 6 vertex graph where it can be done?
Seems to me we are still in the dark as to what the question means. Archinald has not answered my post #6, and Stephen and I have different interpretations.
 
  • #11
haruspex said:
Are you asking Archinald to find the 6 vertex graph where it can be done?
Seems to me we are still in the dark as to what the question means. Archinald has not answered my post #6, and Stephen and I have different interpretations.

True - I support your interpretation, because it seems the most likely and interesting meaning. (and yes, I'd like Archinald to find that graph). My paraphrase of the problem:
##n## people attended a party. In the beginning, all of them had exactly 3 friends among party members. During the party, some people made new friends and at the end of the party everyone had exactly 4 friends among party members. Find all numbers ##n## for which these events are feasible. (Friendship is symmetric: if person A is a friend of person B, then person B is a friend of person A)
(Further, previously unstated assumption: no friendships were broken in the course of the party :-) )
 

1. How do people at a party affect our friendships?

The people we interact with at a party can have an impact on our friendships. Meeting new people or seeing old friends at a party can strengthen or weaken our existing friendships. Additionally, the way we interact with others at a party can also influence our friendships.

2. Is there a limit to how many friends we can have?

The number of friends a person can have is not limited, but it is important to note that we may not have the same level of closeness with all of our friends. Some research suggests that humans can maintain around 150 meaningful relationships at a time, but this number can vary for each individual.

3. How can we accurately count our friends?

Counting friends can be subjective and can vary depending on how we define a friend. Some people may consider acquaintances as friends, while others may only count their closest and most trusted companions. It is important to remember that the quality of our friendships is more important than the quantity.

4. Can attending parties help us make new friends?

Yes, attending parties can be a great way to meet new people and potentially make new friends. Parties often provide a relaxed and social setting where people can interact and get to know each other. However, forming a true friendship takes time and effort beyond just attending one party.

5. Are friendships important for our overall well-being?

Yes, friendships are important for our overall well-being. Studies have shown that having strong and supportive friendships can have a positive impact on our mental and physical health. Friendships can provide emotional support, increase our sense of belonging, and even help us cope with stress and difficult situations.

Suggested for: People at the party and counting friends

Back
Top