|
|
Proginoskes wrote:
> Butch Malahide wrote:
> > Proginoskes wrote:
> > > Butch Malahide wrote:
> > > > Proginoskes wrote:
> > > > > Butch Malahide wrote:
> > > > > > mina_world wrote:
> > > > > > > hello sir~
> > > > > > >
> > > > > > > at a party with 631 people(including me)...
> > > > > > >
> > > > > > > 1) for any three people,
> > > > > > > there is always two people who does not know mutually.
> > > > > > > (namely, two strangers)
> > > > > > >
> > > > > > > 2) if A and B are strangers in 1),
> > > > > > > there is always two people who know A and B in the party.
> > > > > >
> > > > > > I suppose you mean, there are *exactly* two people who know A and B.
> > > > > > (If you mean *at least* two people, then any complete bipartite
> > > > > > graph
> > > > > > with at least two vertices in each part will satisfy your
> > > > > > conditions.) [...]
> > > > >
> > > > > Earlier today, I deduced the same thing, and so the answer can be
> > > > > anywhere between 2 and 629. I didn't manage to solve a more general
> > > > > problem, which I'll sketch below.
> > > > >
> > > > > Call an undirected graph a party graph if it satisfies conditions (1)
> > > > > and (2). Then, which graphs are party graphs?
> > > > >
> > > > >
> > > > > Lemma 1. Suppose G is a party graph without any 5-cycles in it. Then G
> > > > > is bipartite.
> > > > >
> > > > > Proof: If not, then there is an odd cycle C = v_1 v_2 ... v_(2k+1)
> > > > > which has the shortest length among all odd cycles of G. Since G does
> > > > > not contain cycles of length 3 or 5,
> > > > > k >= 3.
> > > > >
> > > > > Now we prove v_1 v_4 is not an edge of G. If so, then v_1 v_4 v_5 ...
> > > > > v_(2k+1) would be an odd cycle of shorter length, contradicting the
> > > > > choice of C.
> > > > >
> > > > > Since G satisfies property (2), there is a vertex w adjacent to v_1
> > > > > and
> > > > > v_4 (since v_1 v_4 is not an edge of G). But then v_1 v_2 v_3 v_4 w
> > > > > v_1
> > > > > is a closed walk of length 5, which shows that there is an odd cycle
> > > > > of
> > > > > length 3 or 5 in G, contradicting the assumptions on G.
> > > > >
> > > > > Therefore G cannot contain a minimal odd cycle of length >= 7, and
> > > > > hence no odd cycles of length >= 7. Since G doesn't have any cycles of
> > > > > length 3 or 5, this makes G bipartite. QED.
> > > > >
> > > > >
> > > > > Lemma 2. If G is a bipartite party graph, then G is a complete
> > > > > bipartite graph with at least 2 vertices in each bipartition.
> > > > >
> > > > > Proof: Let (A,B) be the bipartition, and suppose a is in A, and b is
> > > > > in
> > > > > B. Then ab is an edge of G; otherwise, there would exist a vertex w
> > > > > such that aw and wb are edges of B (by (2)). But w cannot be in A
> > > > > (being adjacent to a) or B (being adjacent to b). Thus, G contains
> > > > > every possible edge between A and B. If A has one vertex u, let v and
> > > > > w
> > > > > be vertices in B; then there are no vertices other than u which is
> > > > > adjacent to v and w. QED.
> > > > >
> > > > >
> > > > > Lemma 3. If G is a complete bipartite graph with at least 2 vertices
> > > > > in
> > > > > each bipartition, then G is a party graph. (Proof: Verify (1) and
> > > > > (2).)
> > > > >
> > > > >
> > > > > These lemmas ask for a resolution to the question: If G contains a
> > > > > 5-cycle, then can G be a party graph?
> > > > >
> > > > > I started analyzing this but reached my limit without paper. If the
> > > > > 5-cycle is 1 2 3 4 5 (I'm dropping the "v_" for convenience), then 1
> > > > > and 3 are nonadjacent. Therefore, there are two vertices such that are
> > > > > adjacent to 1 and 3. One is 2; we call the other one 6. Then 6 is not
> > > > > adjacent to 2, 4, or 5 (by (1)). Then if we consider other non-edges
> > > > > of
> > > > > G, there might be a short proof that G can't be a party graph, based
> > > > > on
> > > > > only looking at a few vertices. Or not.
> > > >
> > > > Take C_5 and split each vertex in two, obtaining a graph with 10
> > > > vertices and 20 edges. This graph contains 5-cycles, it contains no
> > > > 3-cycles, and any two nonadjacent vertices have either 2 or 4 common
> > > > neighbors.
> > >
> > > I wondered whether that would work. But now: Are there any others?
> >
> > Here is a better example: the vertices are the 16 binary words of
> > length 4, two vertices are adjacent if their Hamming distance is 1 or
> > 4. (In other words, we start with the cube Q_4 and add edges joining
> > opposite corners.) This graph has 5-cycles but no 3-cycles, and any two
> > nonadjacent vertices have *exactly* 2 common neighbors.
>
> You know what I'm going to say, don't you? 8-)
>
> Is there any hope that there is a complete characterization of party
> graphs? It's really too bad that there are party graphs with 5-cycles
> in them; it would have made a good Graph Theory problem.
Triangle-free simple graphs, such that every pair of non-adjacent
vertices has exactly two common neighbors, are discussed (as a special
case of "strongly regular graphs") in Douglas West's "Introduction to
Graph Theory", Second Edition: see Exercise 1.3.33 on p. 50, Example
8.6.38 on p. 466, and Exercise 8.6.23 on p. 469. According to West, it
is [as of 2001] an open problem whether there are infinitely many such
graphs. Besides the examples mentioned in this thread, one more is
known: it is 10-regular, has 56 vertices, and is called "the Gewirtz
graph". (By the way, the 5-regular 16-vertex graph, obtained by adding
to the cube Q_4 edges joining opposite corners, is called "the Clebsch
graph". It has the property that deleting a vertex and its neighbors
leaves the Petersen graph.)
|
|