A Skoda
email: alexandre.skoda@univ-paris1.fr

Inheritance of Convexity for the P min -Restricted Game

Keywords: cooperative game, convex game, restricted game, partitions AMS Classification: 91A12, 91A43, 90C27, 05C75

We consider restricted games on weighted graphs associated with minimum partitions. We replace in the classical definition of Myerson restricted game the connected components of any subgraph by the subcomponents corresponding to a minimum partition. This minimum partition P min is induced by the deletion of the minimum weight edges. We provide a characterization of the graphs satisfying inheritance of convexity from the underlying game to the restricted game associated with P min .

Introduction

We consider on a given finite set N with |N | = n a weighted network, i.e., a weighted graph G = (N, E, w) where w is a weight function defined on the set E of edges of G. For a given subset A of N , we denote by E(A) the set of edges in E with both end-vertices in A, by Σ(A) the subset of edges of minimum weight in E(A), and by σ(A) the minimum edge-weight in E(A). Let G A be the graph induced by A, i.e., G A = (A, E(A)). Then GA = (A, E(A) \ Σ(A)) is the graph obtained by deleting the minimum weight edges in G A . In [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF] we introduced the correspondence P min on N which associates to every subset A ⊆ N , the partition P min (A) of A into the connected components of GA . Then for every game (N, v) we defined the restricted game (N, v) associated with P min by:

(1)

v(A) = F ∈P min (A)
v(F ), for all A ⊆ N.

We more simply refer to this game as the P min -restricted game. v is the characteristic function of the game, v : 2 N → IR, A → v(A) and satisfies v(∅) = 0. Compared to the initial game (N, v), the P min -restricted game (N, v) takes into account the combinatorial structure of the graph and the ability of players to cooperate in a given coalition and therefore differents aspects of cooperation restrictions. In particular, assuming that the edgeweights reflect the strengths of relationships between players, P min (A) gives a partition of a coalition A into subgroups where players are in privileged relationships (with respect to the minimum relationship strength in G A ). Many other correspondences have been considered to define restricted games (see, e.g., [START_REF] Myerson | Graphs and cooperation in games[END_REF]; [START_REF] Algaba | A unified approach to restricted games[END_REF]; [START_REF] Bilbao | Cooperative games on combinatorial structures[END_REF][START_REF] Bilbao | Cooperative games under augmenting systems[END_REF]; [START_REF] Faigle | Cores of games with restricted cooperation[END_REF]; [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF]; [START_REF] Grabisch | The core of games on ordered structures and graphs[END_REF]). For a given correspondence a classical problem is to study the inheritance of basic properties as superadditivity and convexity from the underlying game to the restricted game. Inheritance of convexity is of particular interest as it implies that good properties are inherited, for instance the non-emptiness of the core, and that the Shapley value is in the core. For the correspondence P min , we proved in [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF]) that we always have inheritance of superadditivity from (N, v) to (N, v). Let us observe that inheritance of convexity is a strong property. Hence it would be useful to consider weaker properties than convexity. Following alternative definitions of convexity in combinatorial optimization and game theory when restricted families of subsets are considered (not necessarily closed under union and intersection), see, e.g., [START_REF] Edmonds | A min-max relation for submodular functions on graphs[END_REF][START_REF] Faigle | Cores of games with restricted cooperation[END_REF][START_REF] Fujishige | Submodular Functions and Optimization[END_REF] we introduced in [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF] the F-convexity by restricting convexity to the family F of connected subsets of G. In [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF], we have characterized inheritance of F-convexity for P min by five necessary and sufficient conditions on the edge-weights. Of course the study of inheritance of F-convexity is also a first key step to characterize inheritance of convexity in the general case. Moreover, in [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF] and [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF], simple examples with only two or three different weights point out that inheritance of convexity can only happen for a very restricted family of graphs and therefore that we have to consider F-convexity if we wish to obtain results for a sufficiently large family of graphs. We have also highlighted in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF] a relation between Myerson's restricted game introduced in [START_REF] Myerson | Graphs and cooperation in games[END_REF] and the P min -restricted game. Myerson's restricted game (N, v M ) is defined by v M (A) = F ∈P M (A) v(F ) for all A ⊆ N , where P M (A) is the set of connected components of G A . We proved that inheritance of convexity for Myerson's restricted game is equivalent to inheritance of F-convexity for the P min -restricted game associated with a weighted graph with only two different weights. In the present paper, we consider inheritance of convexity for the correspondence P min . As convexity implies F-convexity, the conditions established in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF] are necessary. Now dealing with disconnected subsets of N , we establish supplementary necessary conditions for convex-ity. As it was foreseeable by taking into account examples of [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF] and [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF], we get very strong restrictions on edgeweights and on the combinatorial structure of the graph G. In particular, we obtain that edge-weights can have at most three different values and that many cycles must be complete or dominated (in some sense) by two specific vertices. In the case of three different values σ 1 < σ 2 < σ 3 , there exists only one edge e 1 of minimum weight σ 1 and all edges of weight σ 2 are incident to the same end-vertex of e 1 . We give a complete characterization of these connected weighted graphs in Theorems 24, 25 and 27. Though these graphs are very particular, they seem quite interesting. For instance, when there are only two values and at least two minimum weight edges we obtain weighted graphs similar to the ones defined in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF]) relating Myerson's restricted game to the P min -restricted game.

The article is organized as follows. In Section 2, we give preliminary definitions and results established in [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF]. In particular, we recall the definition of convexity, F-convexity and general conditions on a correspondence to have inheritance of superadditivity, convexity or F-convexity. In Section 3 we recall necessary and sufficient conditions on the weight vector w established in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF] for the inheritance of F-convexity from the original communication game (N, v) to the P minrestricted game (N, v). In Section 4, we establish new very restrictive conditions on a weighted graph to have inheritance of convexity with P min . In Section 5, we prove that these conditions are sufficient.

Preliminary definitions and results

Let N be a given set. We denote by 2 N the set of all subsets of N . A game (N, v) is zero-normalized if v(i) = 0 for all i ∈ N . A game (N, v) is superadditive if, for all A, B ∈ 2 N such that A ∩ B = ∅, v(A ∪ B) ≥ v(A) + v(B). For any given subset ∅ = S ⊆ N , the unanimity game (N, u S ) is defined by:

(2) u S (A) = 1 if A ⊇ S, 0 otherwise.

We note that u S is superadditive for all S = ∅.

Let us consider a game (N, v). For arbitrary subsets A and B of N , we define the value:

∆v(A, B) := v(A ∪ B) + v(A ∩ B) -v(A) -v(B).
A game (N, v) is convex if its characteristic function v is supermodular, i.e., ∆v(A, B) ≥ 0 for all A, B ∈ 2 N . We note that u S is supermodular for all S = ∅. Let F be a weakly union-closed family1 of subsets of N such that ∅ / ∈ F. A game v on 2 N is said to be F-convex if ∆v(A, B) ≥ 0, for all A, B ∈ F such that A ∩ B ∈ F. Let us note that a game (N, v) is convex if and only if it is superadditive and F-convex with F = 2 N \ {∅}.

For a given graph G = (N, E), we say that a subset

A ⊆ N is connected if the induced graph G A = (A, E(A)) is connected.
For a given correspondence P on N and subsets A ⊆ B ⊆ N , we denote by P(B) |A the restriction of the partition P(B) to A.

We recall the following results established in [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF].

Theorem 1. Let N be an arbitrary set and P a correspondence on N . The following conditions are equivalent:

1) For all ∅ = S ⊆ N , the P-restricted game (N, u S ) is superadditive.

2) For all subsets A ⊆ B ⊆ N , P(A) is a refinement of P(B) |A .

3) For all superadditive game (N, v) the P-restricted game (N, v) is superadditive.

As for all A ⊆ B ⊆ N , P min (A) is a refinement of P min (B) |A , Theorem 1 implies the following result.

Corollary 2. Let G = (N, E, w) be an arbitrary weighted graph. Then for every superadditive game (N, v), the P min -restricted game (N, v) is superadditive.

Theorem 3. Let N be an arbitrary set and P a correspondence on N . If for all ∅ = S ⊆ N , the P-restricted game (N, u S ) is superadditive, then the following claims are equivalent.

1) For all ∅ = S ⊆ N , the P-restricted game (N, u S ) is F-convex.

2) For all i ∈ N , for all A ⊆ B ⊆ N \ {i} such that A, B, and A ∪ {i} are in F, and for all A ′ ∈ P(A ∪ {i}) |A , P(A)

|A ′ = P(B) |A ′ .
We also recall the following lemmas proved in [START_REF] Grabisch | Games induced by the partitioning of a graph[END_REF]. We include the proofs for completeness as these two results are extensively used throughout the paper.

Lemma 4. Let us consider subsets A, B ⊆ N and a partition {B 1 , B 2 , . . . , B p } of B. If A, B i , and A ∩ B i ∈ F, for all i ∈ {1, . . . , p}, then for every F-convex game (N, v) we have:

(3) v(A ∪ B) + p i=1 v(A ∩ B i ) ≥ v(A) + p i=1 v(B i ).
Proof. We prove the result by induction. ( 3) is obviously satisfied for p = 1. Let us assume it is satisfied for p and let us consider a partition

{B 1 , B 2 , . . . , B p , B p+1 } of B. We set B ′ = B 1 ∪ B 2 ∪ . . . ∪ B p .
The Fconvexity of v applied to A ∪ B ′ and B p+1 provides the following inequality:

(4) v((A ∪ B ′ ) ∪ B p+1 ) + v((A ∪ B ′ ) ∩ B p+1 ) ≥ v(A ∪ B ′ ) + v(B p+1 ).
By induction (3) is valid for B ′ :

(5)

v(A ∪ B ′ ) + p i=1 v(A ∩ B i ) ≥ v(A) + p i=1 v(B i ).
Adding ( 4) and ( 5) we obtain the result for p + 1.

Lemma 5. Let us consider a correspondence P on N and subsets A ⊆ B ⊆ N such that P(A) = P(B) |A . If A ∈ F and if all elements of P(A) and P(B) are in F, then for every F-convex game (N, v) we have:

(6) v(B) -v(B) ≥ v(A) -v(A). Proof. If P(B) = {B 1 , B 2 , . . . , B p } then P(A) = {A∩B 1 , A∩B 2 , . . . , A∩B p },
and Lemma 4 implies (6).

Finally, we recall a characterization of inheritance of convexity for Myerson's correspondence P M . Theorem 6. (van den [START_REF] Van Den Nouweland | On the convexity of communication games[END_REF]. Let G = (N, E) be a graph. For every convex game (N, v), the Myerson restricted game (N, v M ) is convex if and only if G is cycle-complete.

Inheritance of F-convexity

Let G = (N, E, w) be a weighted graph and let F be the family of connected subsets of N . In this section we recall necessary and sufficient conditions on the weight vector w established in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF] for the inheritance of F-convexity from the original communication game (N, v) to the P minrestricted game (N, v). We assume that all weights are strictly positive and denote by w k or w ij the weight of an edge e k = {i, j} in E.

A star S k corresponds to a tree with one internal vertex and k leaves. We consider a star S 3 with vertices 1, 2, 3, 4 and edges e 1 = {1, 2}, e 2 = {1, 3} and e 3 = {1, 4}.

Star Condition. For every star of type S 3 of G, the edge-weights w 1 , w 2 , w 3 satisfy, after renumbering the edges if necessary:

w 1 ≤ w 2 = w 3 .
Path Condition. For every elementary path γ = (1, e 1 , 2, e 2 , 3, . . . , m, e m , m + 1) in G and for all i, j, k such that 1 ≤ i < j < k ≤ m, the edge-weights satisfy:

w j ≤ max(w i , w k ).

Weak Cycle Condition.

For every simple cycle of G, C = {1, e 1 , 2, e 2 , . . . , m, e m , 1} with m ≥ 3, the edge-weights satisfy, after renumbering the edges if necessary:

(7) w 1 ≤ w 2 ≤ w 3 = • • • = w m = M
where M = max e∈E(C) w(e).

Intermediary Cycle Condition.

1) Weak Cycle condition.

2) Moreover w(e) ≤ w 2 for all chord incident to 2, and w(e) ≤ M = max e∈ Ê(C) w(e) for all chord non-incident to 2. Moreover:

• If w 1 ≤ w 2 < M then w(e) = M for all e ∈ Ê(C) non-incident to 2. If e is a chord incident to 2 then w 1 ≤ w 2 = w(e) < M or w(e) < w 1 = w 2 < M . • If w 1 < w 2 = M , then w(e) = M for all e ∈ Ê(C) \ {e 1 }.
Cycle Condition.

1) Weak Cycle condition.

2) Moreover w(e) = w 2 for all chord incident to 2, and w(e) = M for all e ∈ Ê(C) non-incident to 2.

Proposition 8. Let G = (N, E, w) be a weighted graph.

1) If G satisfies the Path condition then the Weak Cycle condition is satisfied.

2) If G satisfies the Star and Path conditions then the Intermediary Cycle condition is satisfied.

3) If for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is F-convex, then the Cycle Condition is satisfied.

Weak Pan Condition. For all connected subgraphs corresponding to the union of a simple cycle C = {e 1 , e 2 , . . . , e m } with m ≥ 3, and an elementary path P such that there is an edge e in P with w(e) ≤ min 1≤k≤m w k and |V (C) ∩ V (P )| = 1, the edge-weights satisfy:

(a) either

w 1 = w 2 = w 3 = • • • = w m = M , (b) or w 1 = w 2 < w 3 = • • • = w m = M ,
where M = max e∈ Ê(C) w(e). In this last case V (C) ∩ V (P ) = {2}.

Pan Condition.

1) Weak Pan condition.

2) If Claim (b) of the Weak Pan condition is satisfied and if moreover w(e) < w 1 then {1, 3} is a maximum weight chord of C.

Proposition 9. Let G = (N, E, w) be a weighted graph.

1) If G satisfies the Star, and Path conditions, then the Weak Pan condition is satisfied.

2) If for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is F-convex, then the Pan Condition is satisfied.

We say that two cycles are adjacent if they share at least one common edge.

Lemma 10. Let G = (N, E, w) be a weighted graph satisfying the Star and Path conditions. Then for all pairs (C, C ′ ) of adjacent simple cycles in G, we have:

(8) M = max e∈ Ê(C) w(e) = max e∈E(C) w(e) = max e∈E(C ′ ) w(e) = max e∈ Ê(C ′ )
w(e) = M ′ .

Proof. We first consider M = max e∈E(C) w(e) and M ′ = max e∈E(C ′ ) w(e).

Let us consider two adjacent cycles C and C ′ with M < M ′ . There is at least one edge e 1 common to C and C ′ . Then we have w 1 ≤ M < M ′ and therefore e 1 is a non-maximum weight edge in C ′ . By Claim 1 of Proposition 8 the Weak Cycle condition is satisfied. It implies that there are at most two non-maximum weight edges in C ′ . Therefore there exists an edge e ′ 2 in C ′ adjacent to e 1 with w ′ 2 = M ′ . As M ′ > M , e ′ 2 is not an edge of C. Let e 2 be the edge of C adjacent to e 1 and e ′ 2 . Then we have w 2 ≤ M < M ′ but it contradicts the Star condition applied to {e 1 , e 2 , e ′ 2 }. Therefore M = M ′ . Finally by Claim 2 of Proposition 8 the Intermediary Cycle condition is satisfied and we have M = M = M ′ = M ′ .

Adjacent Cycles Condition. For all pairs (C, C ′ ) of adjacent simple cycles in G such that: 2 ∈ E(C ′ ) \ E(C) such that e 1 , e 2 , e ′ 2 are adjacent and:

(a) V (C) \ V (C ′ ) = ∅ and V (C ′ ) \ V (C) = ∅,
• w 1 = w 2 = w ′ 2 if |E(C)| ≥ 4 and |E(C ′ )| ≥ 4. • w 1 = w 2 ≥ w ′ 2 or w 1 = w ′ 2 ≥ w 2 if |E(C)| = 3 or |E(C ′ )| = 3.
Proposition 11. Let G = (N, E, w) be a weighted graph. If for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is F-convex, then the Adjacent Cycles Condition is satisfied.

Finally the following characterization of inheritance of F-convexity was established in [START_REF] Skoda | Convexity of Network Restricted Games Induced by Minimum Partitions[END_REF].

Theorem 12. Let G = (N, E, w) be a weighted graph. For every superadditive and F-convex game (N, v), the P min -restricted game (N, v) is F-convex if and only if the Path, Star, Cycle, Pan, and Adjacent cycles conditions are satisfied.

Inheritance of convexity

We consider in this section inheritance of convexity. As convexity implies superadditivity and F-convexity, the conditions established in Section 3 are necessary. We now have to deal with disconnected subsets of N . We establish supplementary necessary conditions implying strong restrictions on edge-weights. In particular, we obtain that edge-weights can have at most three different values.

Lemma 13. Let G = (N, E, w) be a weighted graph and let us assume that for all ∅ = S ⊆ N the P min -restricted game (N, u S ) is convex. Let e 1 = {1, 2} and e 2 = {2, 3} be two adjacent edges, and e be an edge such that:

(9) max(w 1 , w 2 ) < w(e).

Then there exists an edge e ′ ∈ E linking e to vertex 2. Moreover, if w 1 = w 2 , then we have either w 1 < w 2 = w(e ′ ) or w 2 < w 1 = w(e ′ ). Otherwise, we have w(e ′ ) ≤ w 1 = w 2 .

Proof. We set e = {j, k}. Star condition implies j = 2 and k = 2 (otherwise we get a contradiction with (9)). By contradiction, let us assume that there is no edge linking e to 2. We can assume w 1 ≤ w 2 < w(e). Let us define the following subsets of N , A 1 = {2}, A 2 = {j, k}, A = A 1 ∪A 2 , and B = A∪{1} as represented in Figure 52. We set i = 3. Hence A ⊆ B ⊆ N \ {i}. As

j k 1 2 3 e e 1 e 2 A 2 A 1 =i B Figure 1: w 1 ≤ w 2 < w(e).
there is no edge linking e to 2, we have P min (A) = {{2}, {j}, {k}}. Let us note that, as w 2 < w(e), there is always a component

A ′ of P min (A ∪ {i}) containing A 2 . As w 1 < w(e),
w 3 w 3 w 3 w 3 w 2 w 2 w 2 w 2 w 1 w 2 Figure 3: w 1 < w 2 < w 3 .
Lemma 14. Let G = (N, E, w) be a weighted graph and let us assume that for all ∅ = S ⊆ N the P min -restricted game (N, u S ) is convex. Let e 1 = {1, 2} and e 2 = {2, 3} be two adjacent edges and let e and e ′ be two edges in E such that:

(10) max(w 1 , w 2 ) < min(w(e), w(e ′ )).

Then w(e) = w(e ′ ).

Proof. Let us first assume e ′′ = {2 ′ , 2 ′′ } as represented in Figure 5. As w ′ 2 < w(e) (resp. w ′′ 2 < w(e ′ )), Star condition applied to {e ′ 2 , e, e ′′ } (resp. {e ′′ 2 , e ′ , e ′′ }) implies w(e ′′ ) = w(e) (resp. w(e ′′ ) = w(e ′ )) and then w(e) = w(e ′ ), a contradiction.

2 ′ 2 ′′ 1 2 3 e e ′ e ′′
Let us now assume e ′ = {1 ′ , 2 ′′ } and e ′′ = {1 ′ , 2 ′ } as represented in Figure 6. Then there is a cycle C = {2, e ′ 2 , 2 ′ , e ′′ , 1 ′ , e ′ , 2 ′′ , e ′′ 2 , 2}. As w ′ 2 < w(e), Star condition applied to {e ′ 2 , e, e ′′ } implies w(e ′′ ) = w(e). As w(e) < w(e ′ ), we get w(e ′′ ) < w(e ′ ). Therefore C has three non-maximum weight edges e ′ 2 , e ′′ 2 , e ′′ , contradicting the Cycle condition.

For a given weighted graph G = (V, E), let {σ 1 , σ 2 , . . . , σ k } be the set of its edge-weights such that σ 1 < σ 2 < . . . < σ k with 1 ≤ k ≤ n. We denote by E i the set of edges in E with weight σ i . 1. There exists a pair of adjacent edges {e 1 , e 2 } such that w 1 = σ 1 and w 2 = σ 2 .

2. Let N 1 be the set of end-vertices of edges with weight σ 1 . The subgraph

G N 1 is connected.
Proof.

1. If there is no such pair then we get a contradiction to the Path condition.

Let us consider two vertices v

′ is a path from v ′ to v ′′ in G N 1 .
The following proposition is a direct consequence of Lemma 14, Proposition 7 and Lemma 15.

Proposition 16. Let G = (N, E, w) be a connected weighted graph and let us assume that for all ∅ = S ⊆ N the P min -restricted game (N, u S ) is convex. Then the edge-weights have at most three different values

σ 1 < σ 2 < σ 3 . Moreover, if |E 1 | ≥ 2, then the edge-weights have at most two different values σ 1 < σ 2 .
Of course, Proposition 16 implies that if the edge-weights have three different values, then there is only one edge with weight σ 1 .

Proposition 17. Let G = (N, E, w) be a connected weighted graph. Let us assume that for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is convex. Then for all elementary path γ = {1, e 1 , 2, e 2 , . . . , m, e m , m + 1} in G such that w 1 < w m , we have:

(11) max(w 1 , w 2 ) ≤ w 3 = w 4 = • • • = w m .
Proof. As convexity implies F-convexity, Propositions 7 and 8 imply that the Star, Path and Cycle conditions are satisfied. The Path condition implies w j ≤ max(w 1 , w m ) = w m for all j, 1 ≤ j ≤ m. Hence ( 11) is obviously satisfied if m = 3. Let us assume m ≥ 4 and by contradiction w m-1 < w m . The Path condition implies w 2 ≤ max(w 1 , w m-1 ) < w m . Therefore max(w 1 , w 2 ) < w m . Then Lemma 13 implies that there exists an edge e linking e m to 2 with w(e) ≤ max(w 1 , w 2 ). Hence we have w(e) < w m .

Let us first assume e = {2, m} as represented in Figure 7. Then Star A cycle C is said constant if all edges in E(C) have the same weight.

1 2 3 m m + 1 e 1 e 2 em e
Lemma 18 (STRONG PAN CONDITION FOR NON-CONSTANT CY-CLE). Let G = (N, E, w) be a connected weighted graph. Let us assume that for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is convex. Let us consider a simple cycle C m = {1, e 1 , 2, e 2 , . . . , m, e m , 1} and an edge e ∈ E incident to 2, such that:

(12) w(e) < w 1 = w 2 < w 3 = • • • = w m = M = max e∈ Ê(C)
w(e).

Then e is not a chord of C m and C m is a complete cycle.

Proof. Cycle condition implies that any chord of C m incident to 2 has weight w 2 . Therefore e cannot be a chord of C m . Let us set e = {2, m + 1}.

Let us first prove that e ′ j = {2, j} ∈ Ê(C m ) for all j, 4 ≤ j ≤ m. Lemma 13 implies that it is sufficient to prove the existence of such a chord for m = 4. Indeed let us assume e

′ j / ∈ Ê(C m ) for a given index j, 4 ≤ j ≤ m. m + 1 m 1 M M M w 1 w 2 M w(e) Figure 9: w(e) < w 1 = w 2 < w 3 = • • • = w m = M .
Then Lemma 13 applied to e j-1 (resp. e j ) and to the pair of adjacent edges e 1 and e 2 implies that e ′ j-1 (resp. e ′ j+1 ) exists in Ê(C m ). Then we have to prove that e ′ j is a chord in the cycle {2, e ′ j-1 , j -1, e j-1 , j, e j , j + 1, e ′ j+1 , 2} as represented in Figure 10.

w 1 = w 2 < w 3 = • • • = w m = M .
By contradiction let us assume e ′ 4 / ∈ Ê(C 4 ). Pan condition implies that {1, 3} is a maximum weight chord of C 4 . Let us define the following subsets of N , Let us now prove that {j, k} ∈ Ê(C m ) for all pairs of nodes j, k, with 3 ≤ j ≤ m -1 and k = 1 or j + 2 ≤ k ≤ m. We have {2, j} and {2, k} in Ê(C m ). Then we can consider the cycle Cm = {2, e ′ j , j, e j , j + 1, . . . , k, e ′ k , 2} as represented in Figure 12. Then Pan condition applied to Cm and e implies

A 1 = {2, 5}, A 2 = {4}, A = A 1 ∪ A 2 , B = A ∪
j 3 2 k 1 M M M w 1 w 2 M e ′ j e ′ k w(e) Figure 12: Cm = {2, e ′ j , j, e j , j + 1, . . . , k, e ′ k , 2} and w ′ j = w ′ k = w 1 = w 2 .
that {j, k} is a maximum weight chord of Cm .

Remark 1. Let us observe that it results from Propositions 16, 17 and from the Star condition that every pan {C m , P r } such that C m has non constant weights and such that P r has an edge e with w(e) < min e j ∈E(Cm) w j , satisfies the hypothesis of Lemma 18. (In fact P r is necessarily limited to one edge).

Lemma 19. Let G = (N, E, w) be a connected weighted graph. Let us assume that for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is convex.

Let us moreover assume that the edge-weights have exactly three different values σ 1 < σ 2 < σ 3 . Then there exist three edges e 1 , e 2 , e 3 with respective weights σ 1 , σ 2 , σ 3 such that e 1 and e 2 are incident to a node v and e 3 is adjacent to e 1 or e 2 but not incident to v.

Three edges e 1 , e 2 , e 3 satisfying Lemma 19 correspond to three possible situations represented in Figure 13.

w 1 = σ 1 < w 2 = σ 2 < w 3 = σ 3 .
implies w(e ′ ) = σ 2 . Therefore we can substitute e ′ for e 2 and then the 3-tuple {e 1 , e ′ , e 3 } satisfies the conclusion of the lemma.

Lemma 20. Let G = (N, E, w) be a connected weighted graph. Let us assume that for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is convex.

Let us moreover assume that the edge-weights have exactly three different values σ 1 < σ 2 < σ 3 . Then there is only one edge e 1 with weight σ 1 , and all edges with weight σ 2 are incident to the same end-vertex v of e 1 . Moreover, all edges with weight σ 3 are not incident to v but connected to v by e 1 or by an edge with weight σ 2 .

1 2 3 σ 1 σ 2 σ 2 σ 3 σ 2 Figure 15: σ 1 < σ 2 < σ 3 .
Proof. Proposition 16 implies that there is only one edge with weight σ 1 . Lemma 19 implies that there exists e 1 , e 2 , e 3 in E with w i = σ i for i ∈ {1, 2, 3} and such that one of the three situations represented in Figure 13 holds. Let e be an edge in E \ {e 2 } with w(e) = σ 2 and let us assume that e is not incident to 2. Let us first assume e 3 = {3, 4} (Case a in Figure 13). Then e cannot be incident to 3 otherwise {e, e 2 , e 3 } contradicts the Star condition. e cannot be incident to 4 otherwise {e 2 , e 3 , e} contradicts the Path condition. Finally, e cannot be incident to 1 otherwise Proposition 17 applied to {e, e 1 , e 2 , e 3 } implies σ 2 = σ 3 , a contradiction. Let us now assume e 3 = {3, 1} (Case b in Figure 13). Then e cannot be incident to 1 (resp. 3) otherwise {e, e 1 , e 3 } (resp. {e, e 2 , e 3 }) contradicts the Star condition. Finally, if e 3 = {4, 1} (Case c in Figure 13), then we can establish as before with e 3 = {3, 4} that e cannot be incident to 1, 3, and 4.

As G is connected, there exists a shortest path γ linking e to 1, 2 or 3. The Path condition applied to {e} ∪ γ ∪ {e 1 } or {e} ∪ γ ∪ {e 2 } implies that all edges in γ have weight σ 1 or σ 2 . But, as e 1 is the unique edge with weight σ 1 , we get w(e) = σ 2 for any edge e in γ. Let e ′ be the edge of γ incident to 1, 2, or 3. As w(e ′ ) = σ 2 , the first part of the proof implies that e ′ is necessarily incident to 2. If e 3 = {3, 4} (resp. e 3 = {4, 1}), we consider γ ′ = {e} ∪ γ ∪ {e 2 , e 3 } (resp. γ ′ = {e} ∪ γ ∪ {e 1 , e 3 }) as represented in Figure 16 (resp. Figure 18). Then Proposition 17 applied to γ ′ implies σ 2 = σ 3 (resp. σ 1 = σ 3 ), a contradiction. If e 3 = {3, 1}, then we can still consider γ ′ = {e} ∪ γ ∪ {e 1 , e 3 } as represented in Figure 17 and get the same contradiction.

Finally, if an edge with weight σ 3 is incident to v then it contradicts Star condition. Then Lemma 13 implies the result. assume that C4 has no chord otherwise we can replace C4 by a cycle C3 . Moreover, the Adjacent cycles condition implies that such a chordless cycle C3 or C4 is necessarily unique (two adjacent chordless cycles cannot have a common minimum weight edge). We now consider the case where the edge-weights have only two different values.

1 2 3 4 σ 2 e ′ e σ 2 e 1 σ 1 e 2 σ 2 e 3 σ 3 Figure 16: γ ′ = {e} ∪ γ ∪ {e 2 , e 3 }. 3 1 2 σ 2 e ′ e σ 2 e 1 σ 1 e 2 σ 2 e 3 σ 3 Figure 17: γ ′ = {e} ∪ γ ∪ {e 1 , e 3 }.
Proposition 21. Let G = (N, E, w) be a weighted connected graph. Let us assume that for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is convex. Let us moreover assume that the edge-weights have exactly two different values σ 1 < σ 2 . Then, either there exists only one edge e 1 with weight σ 1 or all edges with weight σ 1 are incident to the same vertex v and no edge with weight σ 2 is incident to v.

Two examples corresponding to the two possible situations described in Proposition 21 are represented in Figure 21. Proof. As G is connected there is at least one pair of adjacent edges e 1 = {1, 2}, and e 2 = {2, 3} with weights σ 1 < σ 2 . Let e be an edge in E \ {e 1 } with weight w(e) = σ 1 and let us assume that e is not incident to 1. Then e cannot be incident to 2 otherwise it contradicts the Star condition. As G is connected, there exists a shortest path γ linking e to 1 or 2. The Path condition applied to {e} ∪ γ ∪ {e 1 } implies that all edges in γ have weight σ 1 . Let e ′ be the edge of γ incident to 1 or 2. As w(e ′ ) = σ 1 , the first part of the proof implies that e ′ is necessarily incident to 1. Let us consider γ ′ = {e} ∪ γ ∪ {e 1 , e 2 } as represented in Figure 22. Then Proposition 17

v 1 2 σ 2 σ 1 σ 1 σ 2 σ 2 σ 1 σ 1 σ 2 σ 1 e 1 σ 2 σ 2 σ 2
1 2 3 σ 1 e ′ e σ 1 e 1 σ 1 e 2 σ 2 Figure 22: γ ′ = {e} ∪ γ ∪ {e 1 , e 2 }.
applied to γ ′ implies σ 1 = σ 2 , a contradiction. Therefore e is necessarily incident to 1. Moreover any edge of weight σ 2 incident to 1 would contradict the Star condition.

In the case of three distinct edge-weights σ 1 < σ 2 < σ 3 we establish supplementary necessary conditions on cycles.

Lemma 22. Let G = (N, E, w) be a weighted connected graph. Let us assume that for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is convex. Let us moreover assume that the edge-weights have exactly three different values σ 1 < σ 2 < σ 3 . Let C3 = {1, e 1 , 2, e 2 , 3, e 3 , 1} be a cycle such that w i = σ i for i ∈ {1, 2, 3} . Then there is at most one cycle C 3 adjacent to C3 containing the node 1 (or equivalently with common edge e 3 ). Proof. Proposition 16 implies that e 1 is the unique edge with weight σ 1 . Therefore C3 is a unique cycle with three different edge-weights, otherwise there would be two adjacent cycles with e 1 as a common minimum weight edge contradicting the Adjacent cycles condition. By contradiction, let us assume there exist two triangles adjacent to C3 with common edge e 3 , i.e., we can find two vertices j and k in N such that {1, j}, {1, k}, {3, j}, and {3, k} exist in E. Let us note that these last edges necessarily have weight σ 3 by the Star condition. Let us consider i = 1 and the subsets A 1 = {2}, A 2 = {j, k}, A = A 1 ∪ A 2 , and B = A ∪ {3} as represented in Figure 24. Then P min (A) = {{2}, {j}, {k}}, P min (A ∪ {i}) = {{2}, {1, j, k}} (let us We now establish that if for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is convex, and if a graph contains cycles with constant weights, then a Strong Pan condition is necessary as in Lemma 18 for non constant weights.

j 3 2 k 1 e 1 σ 1 e 2 σ 2 e 3 σ 3 σ 3 σ 3 σ 3 σ 3 =i A 1 A 2 B
Lemma 23 (STRONG PAN CONDITION FOR CYCLES WITH CON-STANT WEIGHTS). Let G = (N, E, w) be a weighted connected graph. Let us assume that for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is convex. Let us moreover assume that the edge-weights have at most three different values σ 1 < σ 2 ≤ σ 3 . Then:

1. If |E 1 | ≥ 2 (and then σ 2 = σ 3 ), then every cycle with constant weight σ 2 is complete.

2. If |E 1 | = 1 with E 1 = {e 1 }
for all j ∈ V (C) \ {2} (resp. {1, j} ∈ E(C) for all j ∈ V (C) \ {1}). 4. If |E 1 | = 1 with E 1 = {e 1
} and e 1 = {1, 2}, then for every cycle C with constant weight σ 2 or σ 3 and not adjacent to e 1 but linked to e 1 by an edge e = {2, k} (of weight σ 2 ) with k ∈ V (C), one of the following conditions is satisfied:

(a) {1, j} ∈ E for all j ∈ V (C).

(b) {2, j} ∈ E for all j ∈ V (C).

(c) There is no edge {2, j} in E with j ∈ V (C) \ {k} and C is complete.

5. Let us assume that the edge-weights have three different values σ 1 < σ 2 < σ 3 . Let e 1 = {1, 2} be the unique edge with weight σ 1 and let us assume that all edges with weight σ 2 are incident to 2. Then every cycle C m which does not contain e 1 is complete. Moreover, if 1 ∈ V (C m ) then m = 3 and such a cycle is unique, has constant weight σ 3 , and is adjacent to a unique triangle C3 which contains the edge e 1 .

Situations corresponding to

2 ′ 2 1 e 1 σ 1 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2
Figure 26: Situation of Claim 4a in Lemma 23. Two nodes i and j in C cannot be both linked to 1 and 2 (cf. Figure 29), otherwise e 1 is a common minimum weight edge of the cycles induced by {1, 2, i} and {1, 2, j} and as σ 1 < σ 2 , it contradicts the Adjacent Cycles condition.

2 ′ 2 1 e 1 σ 1 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 Figure 27: Situation of Claim 4b in Lemma 23. 2 ′ 2 1 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 e 1 σ 1
i

2 ′ 2 1 j e 1 σ 1 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2
Figure 29: i and j linked to 1 and 2.

Remark 4. If the edge-weights have three different edge-weights σ 1 < σ 2 < σ 3 , then it follows from Claim 5 in Lemma 23 that the cycle C m considered in Claim 3 of the same lemma, has to be a triangle (m = 3) (of constant weight σ 3 ). As a triangle has no chord Claim 3 adds nothing in the particular case of three different edge-weights and of a cycle incident to 1. But, a priori, we have to keep this case in Claim 3 to be able to prove Claim 5.

Proof. 1. As |E 1 | ≥ 2, Proposition 16 implies that the edge-weights have at most two different values σ 1 < σ 2 . Proposition 21 implies that all edges with weight σ 1 are incident to the same vertex j and no edge with weight σ 2 is incident to j. Let us consider a cycle C with constant weight σ 2 . Lemma 13 implies that every edge in E 2 is linked to j by an edge in E 1 as represented in Figure 30. Let us consider the Myerson restricted game

j σ 2 σ 2 σ 2 σ 2 σ 2 σ 1 σ 1 σ 1 σ 1
Figure 30: Every edge in E 2 is linked to j by an edge in E 1 .

v M , which corresponds to the partition into connected components. Then

we have v(A ∪ {j}) = v M (A) + v(j) = v M (A) for all A ⊆ N \ {j}. Hence, for i ∈ V (C) and for A ⊆ B ⊆ V (C) \ {i} the inequality: (13) v(B ∪ {j} ∪ {i}) -v(B ∪ {j}) ≥ v(A ∪ {j} ∪ {i}) -v(A ∪ {j})
is equivalent to:

(14) v M (B ∪ {i}) -v M (B) ≥ v M (A ∪ {i}) -v M (A).
As (N, u S ) is convex, ( 13) is satisfied with v = u S . Therefore ( 14) is also satisfied with v = u S and then u M S is convex if we restrict G to V (C). Then Theorem 6 implies that C has to be complete. 2. If there are three different edge-weights, then Lemma 20 implies that there is no cycle with constant weight σ 2 . If E 1 = {e 1 } with e 1 = {1, 2}, let us consider a cycle C with constant weight σ 2 not incident to e 1 and not linked by an edge to e 1 , as represented in Figure 31. For any game (N, v) and for A ⊆ N \ {1, 2} such that there is no edge linking A to {1, 2} we obviously have:

1 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 e 1 σ 1 σ 2 C
(15) v(A ∪ {1, 2}) = v M (A) + v({1}) + v({2}) = v M (A).
Hence, for i ∈ V (C) and for A ⊆ B ⊆ V (C) \ {i}, the subsets A, B, A ∪ {i}, and B ∪ {i} satisfy (15). Then the inequality

v((B ∪ {1, 2}) ∪ {i}) -v(B ∪ {1, 2}) ≥ v((A ∪ {1, 2}) ∪ {i}) -v(A ∪ {1, 2}) is equivalent to: (16) v M (B ∪ {i}) -v M (B) ≥ v M (A ∪ {i}) -v M (A).
Therefore, taking v = u S , we can conclude as in the previous case.

3. Let us consider E 1 = {e ′ 1 } with e ′ 1 = {1 ′ , 2} and a cycle C = {1, e 1 , 2, e 2 , . . . , m, e m , 1} incident to 2. We can assume w.l.o.g. that C has constant weight σ 2 . Note that Proposition 8 implies that the Cycle condition is satisfied, and therefore e ′ 1 cannot be a chord of C. At first we prove that {2, 4} ∈ E. By contradiction let us assume {2, 4} / ∈ E. Let us consider i = 3 and the subsets

A 1 = {4}, A 2 = {1 ′ , 2}, A = A 1 ∪ A 2 , and B = (V (C) \ {i}) ∪ {1 ′ } as represented in Figure 32. Then P min (A) = {{1 ′ }, {2}, {4}} or 4 3 2 1 ′ 1 σ 2 σ 2 σ 2 σ 2 σ 2 e ′ 1 σ 1 =i A 1 A 2 B

Let us consider E

1 = {e ′ 1 } with e ′ 1 = {1 ′ , 2 ′ } and a cycle C = {1, e 1 ,
2, e 2 , 3, . . . , m, e m , 1} with constant weight σ 2 or σ 3 and not incident to e 1 but linked to e 1 by an edge e = {2, 2 ′ } of weight σ 2 .

If e ′ = {2 ′ , j} ∈ E for some j ∈ V (C) \ {2}, then we can consider the cycles C ′ = {2 ′ , e, 2, e 2 , 3, . . . , e j-1 , j, e ′ , 2 ′ } and C ′′ = {2 ′ , e ′ , j, e j , j + 1 . . . , e m , 1, e 1 , 2, e, 2 ′ } as represented in Figure 33. Then C ′ and C ′′ are incident to e ′ 1 and Claim 3 (applied successively to C ′ and C ′′ ) implies that {2 ′ , k} ∈ E for all k ∈ V (C). Hence Claim 4b is satisfied.

22

Documents de travail du Centre d'Economie de la Sorbonne -2017.51 Let us now assume {2 ′ , j} / ∈ E for all j ∈ V (C) \ {2}. If {1 ′ , 2} ∈ E, then we can apply the same reasoning as before (interchanging the roles of 1 ′ and 2 ′ ). Therefore either {1 ′ , k} ∈ E for all k ∈ V (C) and Claim 4a is satisfied or {1 ′ , k} / ∈ E for all k ∈ V (C) \ {2}. Therefore we assume henceforth that the following condition is satisfied:

j 3 2 2 ′ 1 ′ m 1 σ 2 em σ 2 e 1 σ 2 e 2 σ 2 σ 2 e σ 2 e ′ 1 σ 1 e ′ C ′ C ′′
(17)
There is no edge {2 ′ , l} with l ∈ V (C) \ {2} and if {1 ′ , 2} ∈ E there is also no edge {1 ′ , l} with l ∈ V (C) \ {2}.

We now have a proof similar to the one of Claim 3. By contradiction let us assume {2, 4} / (17), {2 ′ , 4} does not exist in E. We have to consider several cases:

∈ E. Let us consider i = 3, A 1 = {4}, A 2 = {1 ′ , 2 ′ , 2}, A = A 1 ∪ A 2 ,
1. If {1 ′ , 2} ∈ E then {1 ′ , 4} / ∈ E by (17) and therefore P min (A) = {{1 ′ , 2, 2 ′ }, {4}}. 2. If {1 ′ , 2} / ∈ E and {1 ′ , 4} ∈ E, then P min (A) = {{1 ′ , 4}, {2, 2 ′ }}. 3. If {1 ′ , 2} / ∈ E and {1 ′ , 4} / ∈ E, then P min (A) = {{1 ′ }, {2, 2 ′ }, {4}}.
In every case P min (A ∪ {i}) = {A ∪ {i}} or {{1 ′ }, A ∪ {i} \ {1 ′ }}. Indeed we have to delete e ′ 1 but 1 ′ may be linked to 2, 3 or 4. We also have

P min (B) = {B} or {{1 ′ }, B \ {1 ′ }}. Therefore taking A ′ = A ∪ {i} or A ∪ {i} \ {1 ′ } we have in every case either P min (B) |A ′ = {A} or {{1 ′ }, A \ {1 ′ }} or {A \ {1 ′ }}. As neither A nor A \ {1 ′ } is in P min (A), we get P min (A) |A ′ = P min (B) |A ′ , contradicting Theorem 3. Hence {2, 4} ∈ E.
Then we can consider the cycle {1, e 1 , 2, e, 4, e 4 , . . . , m, e m , 1} and by the same reasoning {2, 5} ∈ E. Iterating as in the proof of Claim 3 we get {2, j} ∈ Ê(C) for all j ∈ V (C).

Let us now prove that {j, k} ∈ Ê(C) for all pairs of nodes j, k, with 3 ≤ j ≤ m -1 and k = 1 or j + 2 ≤ k ≤ m. By contradiction let us assume {j, k} / ∈ E for two nodes j and k with 3 ≤ j ≤ m -1 and k = 1 or j + 2 ≤ k ≤ m. Let us assume that {1 ′ , j} ∈ E and {1 ′ , k} ∈ E. As e ′ j := {2, j} and e ′ k := {2, k} are in Ê(C), we obtain two adjacent 4-cycles Cj = {2, e ′ j , j, {j, 1 ′ }, 1 ′ , e ′ 1 , 2 ′ , e, 2} and Ck = {2, e ′ k , k, {k, 1 ′ }, 1 ′ , e ′ 1 , 2 ′ , e, 2} without chord (following our assumptions the chords {2 ′ , j}, {2 ′ , k}, {1 ′ , 2} are not in E) with a common edge e ′ 1 of minimum weight σ 1 contradicting the Adjacent cycles condition. Hence we can assume that at most one of the edges {1 ′ , j} or {1 ′ , k} is in E. We now consider the cycle C = {2, e ′ j , j, e j , j+ 1, . . . , k, e ′ k , 2} and subsets 35 and we choose i = 2. Let us observe that to obtain P min (A), P min (A ∪ {i}) or P min (B) we only have to delete the edge e ′ 1 = {1 ′ , 2 ′ } of weight σ 1 . As we know that {1 ′ , j} / ∈ E or {1 ′ , k} / ∈ E, {j, k} cannot be a subset of any component of P min (A), i.e., we cannot have P min (A) = {{1 ′ , j, k}, {2 ′ }} or P min (A) = {{1 ′ }, {2 ′ }, {j, k}} but only P min (A) = {{1 ′ }, {2 ′ }, {j}, {k}} or P min (A) = {{1 ′ , j}, {2 ′ }, {k}} or P min (A) = {{1 ′ , k}, {2 ′ }, {j}}. As {2, j} and {2, k} are in Ê(C) and as i = 2, j and k are connected in G A∪{i}\{1 ′ ,2 ′ } . Hence there exists A ′ ∈ P min (A∪{i}) such that {j, k} ⊆ A ′ . As j and k are in B 1 which is a connected subset of G B\{1 ′ ,2 ′ } there exists B ′ ∈ P min (B) such that {j, k} ⊆ B ′ . Hence {j, k} ⊆ (B ′ ∩ A ′ ) ∈ P min (B) |A ′ . But {j, k} cannot be a subset of any component of P min (A). Hence we have P min (A) |A ′ = P min (B) |A ′ contradicting Theorem 3. Therefore {j, k} ∈ Ê(C) and C is complete. 5. Lemma 20 implies that there is a unique edge e 1 = {1, 2} with weight σ 1 , all edges with weight σ 2 are incident to the same end-vertex 2 of e 1 and all edges with weight σ 3 are not incident to 2 but connected to 2 by e 1 or by an edge with weight σ 2 . We have to consider several cases.

A 1 = {j}, A 2 = {k}, A 3 = {1 ′ , 2 ′ }, A = A 1 ∪A 2 ∪ A 3 , B 1 = V ( C) \ {2}, B 2 = A 3 , and B = B 1 ∪ B 2 as represented in Figure
j 3 2 2 ′ 1 ′ k 1 σ 2 σ 2 σ 2 σ 2 e 1 σ 2 e 2 σ 2 e ′ j e ′ k e σ 2 e ′ 1 σ 1 =i A 1 A 2 B 2 = A 3 B 1
1. Let us assume that C m has non constant weight. As e 1 / ∈ E(C m ), an edge in E(C m ) has weight σ 2 or σ 3 . Edges with weight σ 2 are incident to 2, therefore 2 ∈ V (C m ) and e 1 is adjacent to C m . Then Lemma 18 implies that e 1 is not a chord of C m and C m is complete as represented in Figure 36. i

2 1 σ 3 σ 3 σ 3 σ 2 σ 2 σ 3 σ 3 σ 2 σ 2 σ 2 σ 3 σ 3 σ 3 σ 3 σ 3 e 1 σ 1
2 1 j e 1 σ 1 σ 3 σ 3 σ 3 σ 3 σ 3 σ 2 σ 2 γ γ ′ C m Figure 37: C ′ m = {2, i} ∪ γ ∪ {j, 2} and C ′′ m = {2, i} ∪ γ ′ ∪ {j, 2}.
Therefore C ′ m and C ′′ m are complete. Then {i, j} ∈ E and {2, k} ∈ E for all k ∈ V (C m ). Hence for any pair of nodes i, j in V (C m ), {2, i} and {2, j} exist in E and by the same reasoning as before {i, j} ∈ E. Therefore C m is complete.

Let us now assume 1 ∈ V (C m ). Claim 3 implies that {1, i} ∈ Ê(C m ) for all i ∈ V (C m ). Only the edges of C m incident to 1 are linked to 2 by e 1 . If m ≥ 5, then there exist at least two nodes i and j in V (C m )\{1} such that {2, i} and {2, j} are in E and have weight σ 2 as represented in Figure 38. Then the cycles defined by {2, i}, {i, 1}, e 1 and i 1 2 2 and e ′ 3 have to be linked to node 2. But there can be only one edge e linking 2 to V (C 4 ) \ {1}, otherwise we get a contradiction to the cycles condition as with m ≥ 5. Hence we necessarily have e = {2, 3 ′ } as represented in Figure 39. Then C3 = {1, e 1 , 2, e, 3 ′ , e ′ , 1} is a triangle containing edges with weights σ 1 < σ 2 < σ 3 , and {1, e ′ 1 , 2 ′ , e ′ 2 , 3 ′ , e ′ , 1} and {1, e ′ , 3 ′ , e ′ 3 , 4 ′ , e ′ 4 , 1} are two triangles adjacent to C3 containing the edge e ′ of weight σ 3 . It contradicts Lemma 22. Hence m = 3.

j e 1 σ 1 σ 3 σ 3 σ 3 σ 3 σ 3 σ 3 σ 3 σ 2 σ 2 C m
′ 1 = {1, 2 ′ }, e ′ 2 = {2 ′ , 3 ′ }, 2 ′ 3 ′ 1 2 4 ′ σ 1 e 1 σ 3 e ′ 4 σ 3 e ′ 1 σ 3 e ′ σ 3 e ′ 2 σ 3 e ′ 3 σ 2 e C 4
C 3 = {1, e ′ 1 , 2 ′ , e ′ 2 , 3 ′ , e ′ 3 ,
1} is a triangle with constant weight σ 3 and e ′ 2 is linked to 2 by an edge of weight σ 2 . There is only one edge e linking e ′ 2 to 2 otherwise it contradicts the Adjacent cycles condition as with m ≥ 5. We can assume w.l.o.g. e = {2, 2 ′ } as represented in Figure 40. Hence the triangle C3 = {1, e 1 , 2, e, 2 ′ , e ′ 1 , 1} exists and Lemma 22 implies that C 3 is necessarily unique. C3 is unique as a triangle containing e 1 is necessarily unique (otherwise it contradicts the Adjacent cycles condition).

2 ′ 1 2 3 ′ σ 3 σ 3 σ 3 e 1 σ 1 σ 2 e C 3
Remark 5. If there exists a cycle C4 without chord and containing the edge e 1 of weight σ 1 (such a cycle is unique otherwise it contradicts the Adjacent cycles condition), then Claim 5 of Lemma 23 implies that no cycle of constant weight σ 3 contains vertex 1.

5 Graphs satisfying inheritance of convexity 1. All edges in E 1 are incident to the same vertex 1 and all edges in E 2 are linked to 1 by an edge in E 1 .

One of the two following equivalent conditions is satisfied:

(a) There is inheritance of convexity for the correspondence P M (associated with Myerson's game) on the subgraph

G 1 = (N, E \ E 1 ). (b) G 1 = (N, E \ E 1 ) is cycle-complete.
We give in Figure 41 an example of a graph satisfying conditions 1 and 2 of Theorem 24.

2 3 4 5 6 7 1 σ 1 σ 2 σ 1 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 1 σ 1 σ 2 σ 1
Figure 41: Every edge of weight σ 2 is linked to 1 by an edge of weight σ 1 and the cycle defined by 3, 4, 6, 7 is complete.

Proof. Conditions 2a and 2b are equivalent by Theorem 6 (van den [START_REF] Van Den Nouweland | On the convexity of communication games[END_REF]. By Proposition 21, Lemma 13 and Lemma 23 (Claim 1), conditions 1 and 2 are necessary. We now prove that there are also sufficient. Let us consider a convex game (N, v). We denote by (N, v) (resp. (N, v M )) the restricted game associated with P min (resp. P M ) on G (resp. G 1 ). Let us consider i ∈ N and subsets A ⊆ B ⊆ N \ {i}. We consider several cases.

Let us first assume

i = 1. As A ⊆ B ⊆ N \ {1}, we have E(A) ⊆ E(B
) ⊆ E 2 and hence P min (A) and P min (B) are singleton partitions.

Then (18) v(B ∪ {i}) -v(B) ≥ v(A ∪ {i}) -v(A)
is equivalent to v(B ∪ {i}) ≥ v(A ∪ {i}) and this last inequality is necessarily satisfied as (N, v) is superadditive (cf. Corollary 2 page 4).

2. We assume now i = 1 and A ⊆ N \ {1, i}. Then E(A) ⊆ E(A ∪ {i}) ⊆ E 2 and therefore P min (A) and P min (A ∪ {i}) are singleton partitions. Hence ( 18) is equivalent to v(B∪{i})-v(B) ≥ 0 and this last inequality is necessarily satisfied as (N, v) is superadditive.

Finally, we assume i = 1 and 1 ∈ A.

Let us assume E(A) = ∅. An edge in E(A) has weight σ 1 or σ 2 .

As every edge of weight σ 2 is linked to 1 by an edge of weight σ 1 (by Condition 1) we necessarily have

E(A) ∩ E 1 = ∅. Therefore P min (A) = P M (A) and v(A) = v M (A). Now if E(A) = ∅ then P min (A) = P M (A)
is trivially the singleton partition of A, and we have v

(A) = v M (A) = 0. By the same reasoning we have v(A ∪ {i}) = v M (A ∪ {i}), v(B) = v M (B), and v(B ∪ {i}) = v M (B ∪ {i}). Hence (18) is equivalent to (19) v M (B ∪ {i}) -v M (B) ≥ v M (A ∪ {i}) -v M (A),
and Condition 2 implies that ( 19) is satisfied.

Theorem 25. Let G = (N, E, w) be a weighted connected graph. Let us assume that the edge-weights have only two different values σ 1 < σ 2 . Let us assume |E 1 | = 1. Let e 1 = {1, 2} be the unique edge in E 1 . Then there is inheritance of convexity for the correspondence P min on G if and only if the following conditions are verified:

1. There exists at most one chordless cycle containing e 1 .

2. For every cycle C with constant weight σ 2 either C is complete or all vertices of C are linked to the same end vertex of e 1 .

We give in Figure 42 an example of a graph satisfying conditions 1 and 2 of Theorem 25. Remark 6. Let us observe that Condition 1 of Theorem 25 implies that e 1 cannot be a chord of any cycle of G.

Proof. The Adjacent cycles condition implies that condition 1 is necessary. Lemma 23 (Claims 2, 3, and 4) implies that condition 2 is necessary.

1 2 σ 1 e 1 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2
Figure 42: Either a cycle with constant weight is complete or all its vertices are linked to one end-vertex of e 1 .

We now prove they are sufficient. Let us consider a convex game (N, v), i ∈ N and subsets A ⊆ B ⊆ N \ {i}. We have to prove that the following inequality is satisfied:

(20) v(B ∪ {i}) -v(B) ≥ v(A ∪ {i}) -v(A).
We consider several cases.

1. Let us assume e 1 / ∈ E(A) and e 1 / ∈ E(B). Then we have E(A) ⊆ E(B) ⊆ E 2 and therefore P min (A) and P min (B) are singleton partitions. Then ( 20) is equivalent to v(B ∪ {i}) ≥ v(A ∪ {i}) and this last inequality is necessarily satisfied as (N, v) is superadditive (cf. Corollary 2 page 4).

Let us assume e 1 /

∈ E(A) but e 1 ∈ E(B). Then i / ∈ {1, 2} (otherwise e 1 / ∈ E(B)) and therefore e 1 / ∈ E(A∪{i}). Then P min (A) and P min (A∪ {i}) are singleton partitions and ( 20) is equivalent to v(B ∪ {i})v(B) ≥ 0 and this last inequality is necessarily satisfied as (N, v) is superadditive (cf. Corollary 2 page 4).

3. Let us assume e 1 ∈ E(A). Then we also have e 1 ∈ E(A ∪ {i}), e 1 ∈ E(B), and

e 1 ∈ E(B ∪ {i}). Therefore (20) is equivalent to v M (B ∪ {i}) -v M (B) ≥ v M (A ∪ {i}) -v M (A) (where (N, v M ) is the Myerson's game associated with G 1 = (N, E \ {e 1 })). Let P M (A) = {A 1 , A 2 , . . . , A p } be the partition of A into connected components in G 1 . If there is no link between i and A then P M (A ∪ {i}) = {P M (A), {i}} and v M (A ∪ {i}) -v M (A) = v({i}) = 0. Then (20) is equivalent to v(B ∪{i})-v(B)
≥ 0 and this last inequality is necessarily satisfied as (N, v) is superadditive. Otherwise we can assume that for some integer r ≤ p, and after reordering if necessary, A 1 , A 2 , . . . , A r are linked to i and the other components of P M (A) are not linked to i.

Hence P M (A ∪ {i}) = {A 1 ∪ . . . ∪ A r ∪ {i}, A r+1 , .
. . , A p } and we have:

(21) v M (A ∪ {i}) -v M (A) = v(A 1 ∪ . . . ∪ A r ∪ {i}) - r j=1 v(A j ).
By the same way, we can assume P M (B) = {B 1 , B 2 , . . . , B q } and P M (B ∪ {i}) = {B 1 ∪ . . . ∪ B s ∪ {i}, B s+1 , . . . , B q } with 1 ≤ s ≤ q.

Then we have:

(22) v M (B ∪ {i}) -v M (B) = v(B 1 ∪ . . . ∪ B s ∪ {i}) - s j=1 v(B j ).
Therefore we have to prove:

(23) v(B ′ ∪ {i}) - s j=1 v(B j ) ≥ v(A ′ ∪ {i}) - r j=1 v(A j ),
where

A ′ = A 1 ∪ . . . ∪ A r and B ′ = B 1 ∪ . . . ∪ B s . Let us observe that obviously P M (A) is a refinement of P M (B) |A .
To achieve the proof we need the following lemma.

Lemma 26. Condition 2 on cycles with constant weight σ 2 implies P M (B) |A ′ = P M (A) |A ′ , i.e., A j ⊆ B j , for all j, 1 ≤ j ≤ r and r ≤ s, after renumbering if necessary.

Proof. By contradiction, let us assume that two components A 1 and A 2 of P M (A) |A ′ are subsets of the same component B 1 ∈ P M (B), after renumbering if necessary. Let ẽ1 = {i, k 1 } (resp. ẽ2 = {i, k 2 }) be an edge linking i to A 1 (resp. A 2 ). As i / ∈ {1, 2}, we have ẽ1 = e 1 and ẽ2 = e 1 , and therefore ẽ1 and ẽ2 have weight σ 2 . As B 1 is connected, there exists an elementary path

γ in B 1 linking k 1 ∈ A 1 to k 2 ∈ A 2 . Note that P M (B) is a partition of B in G 1 = (N, E \ {e 1 }), therefore any edge in B 1 has weight σ 2 . We obtain a simple cycle C = {i, ẽ1 , k 1 } ∪ γ ∪ {k 2 , ẽ2 , i} of constant weight σ 2 . If C is complete, the edge {k 1 , k 2 } is a chord of C. Condition 1 and Remark 6 imply {k 1 , k 2 } = e 1 . Then {k 1 , k 2 } links A 1 to A 2 in G 1 , a contradiction. If C is not complete,
then by Condition 2 all vertices of C are linked to the same end vertex of e 1 . We can assume w.l.o.g. that they are linked to vertex 1 as represented in Figure 43. As e 1 ∈ E(A) and as k 1 and k 2 are in A, we have {1, k 1 } and {1, k 2 } in E(A). We also have {1, k 1 } = e 1 and {1, k 2 } = e 1 , otherwise e 1 would be a chord of a cycle contradicting Remark 6. Then A 1 and A 2 are part of a connected component of A in G 1 , a contradiction.

We can now end the proof of Theorem 25. By Lemma 26, P M (B) |A ′ = P M (A) |A ′ , and as A ′ ⊆ B ′ , we have P M (B ′ ) |A ′ = P M (A ′ ). Then Lemma 5 applied to P M implies that we have for (N, v):

(24) v(B ′ ) - s j=1 v(B j ) ≥ v(A ′ ) - r j=1 v(A j ), 30
Documents de travail du Centre d'Economie de la Sorbonne -2017.51

k 1 i 1 2 k 2 σ 2 ẽ1 σ 2 ẽ2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 2 σ 1 e 1 σ 2 σ 2 σ 2 A 1 A 2 B 1 Figure 43: e 1 in E(A) and k 1 in A 1 , k 2 in A 2 .
with

B ′ = B 1 ∪ . . . ∪ B s and A ′ = A 1 ∪ . . . ∪ A r .
The convexity of (N, v) also implies:

(25) v(B ′ ∪ {i}) -v(B ′ ) ≥ v(A ′ ∪ {i}) -v(A ′ ).
Adding ( 24) and ( 25) we obtain (23).

Graphs with three edge-weights

We now consider the case of a weighted graph with three different edgeweights.

Theorem 27. Let G = (N, E, w) be a weighted connected graph. Let us assume that the edge-weights have only three different values σ 1 < σ 2 < σ 3 . Then there is inheritance of convexity for P min on G if and only if the following conditions are satisfied:

1. There exists only one edge e 1 = {1, 2} of weight σ 1 .

2. An edge in E \ {e 1 } has weight σ 2 if and only if it is incident to the same end-vertex 2 of e 1 .

3. Every edge of weight σ 3 is connected to 2 by e 1 or by an edge of weight σ 2 .

4. There exists at most one (chordless) cycle Cm with m = 3 or 4 containing e 1 .

5. Every cycle C m which does not contain e 1 is complete. Proof of theorem 27. We only have to prove that Conditions 1 to 6 are sufficient. Let us consider a convex game (N, v), i ∈ N and subsets A ⊆ B ⊆ N \ {i}. We have to prove that the following inequality is satisfied:

(26) v(B ∪ {i}) -v(B) ≥ v(A ∪ {i}) -v(A).
Let us note that if i is not linked to A then ( 26) is trivially satisfied as (N, v) is superadditive (Corollary 2). We thereafter assume that i is linked to A by at least one edge. We consider several cases.

Case 1 Let us assume e 1 ∈ E(A).

As e 1 ∈ E(A), we also have e 1 ∈ E(A∪{i}), e 1 ∈ E(B), and e 1 ∈ E(B ∪{i}).

Then ( 26) is equivalent to:

(27) v M (B ∪ {i}) -v M (B) ≥ v M (A ∪ {i}) -v M (A)
where (N, v M ) is the Myerson's game associated with G 1 = (N, E \ {e 1 }).

Conditions 1 to 5 imply that G 1 is cycle-complete (cf. Remark 7). Then, (N, v M ) is convex by Theorem 6, and therefore ( 27) is satisfied.

Case 2 Let us assume i = 1, 2 ∈ A, and 1 / ∈ B. Then we have i / ∈ {1, 2}, e 1 / ∈ E(A), e 1 / ∈ E(A ∪ {i}), e 1 / ∈ E(B), and e 1 / ∈ E(B ∪ {i}). If E(A) = ∅, then Condition 3 implies that every edge e ∈ E(A) of weight σ 3 is linked to 2 by an edge e ′ ∈ E(A) ∩ E 2 (as e 1 / ∈ E(A), e 1 cannot link 2 ∈ A to e). Hence E(A)∩E 2 = ∅ and σ(A) = σ 2 . Then P min (A) is obtained by deleting edges of E 2 in E(A) and corresponds to the partition P M (A) into connected components in the graph G3 := (N, E 3 ). Therefore we have v(A) = v M (A) where (N, v M ) is the Myerson's game associated with G3 . Now if E(A) = ∅, then P min (A) = P M (A) is trivially the singleton partition of A, and we have v(A) = v M (A). By the same reasoning we have

v(A ∪ {i}) = v M (A ∪ {i}), v(B) = v M (B), and v(B ∪ {i}) = v M (B ∪ {i}).
Hence ( 26) is equivalent to :

(28) v M (B ∪ {i}) -v M (B) ≥ v M (A ∪ {i}) -v M (A).
Let C m be a cycle of G3 . Condition 2 implies that 2 is an isolated vertex in G3 . Then 2 / ∈ C m and Condition 5 claims that C m is complete. Hence G3 is cycle-complete. Then, (N, v M ) is convex by Theorem 6 and ( 28) is satisfied. Let us note that Conditions 2 and 3 imply that any edge in G 1 is either incident to 1 or 2 or linked to 2 by an edge of weight σ 2 . Therefore the set of connected components of B (resp. B ∪ {i}) in G 1 is only made up of one component containing 1, one component containing 2, and possibly singleton components (the components containing 1 and 2 may also coincide or be reduced to singletons). Let B 1 (resp. B 2 ) be the connected component of B in G 1 containing vertex 1 (resp. 2). Let B ′ ∪ {i} be the connected component of B ∪ {i} in G 1 containing i. Note that i is necessarily linked by at least one edge to B 1 or B 2 and we have

B 1 ⊆ B ′ , or B 2 ⊆ B ′ , or B 1 ∪ B 2 ⊆ B ′ .
Let us first assume i not linked to B 2 . Then i is necessarily linked to B 1 and Conditions 2 and 3 imply that {1, i} is the unique edge linking i to B. As 1 / ∈ A, i is not linked to A, a contradiction. Let us now assume i linked to B 2 . Let us first suppose B 1 = B 2 (i.e., there exists a chordless cycle C 3 or C 4 in G containing e 1 ). Then B ′ = p j=2 B j where B 2 , B 3 , . . . , B p are the connected components of B in G 1 linked to i (note that B 3 , . . . , B p are singletons). We obtain:

(29) v(B ∪ {i}) -v(B) = v   p j=2 B j ∪ {i}   -v(B 2 ).
Let us now suppose B 1 = B 2 . If i is not linked to B 1 (but linked to B 2 ), then we still have B ′ = p j=2 B j where B 2 , B 3 , . . . , B p are the connected components of B in G 1 linked to i and ( 29) is also satisfied. Finally if i is linked to B 1 (and B 2 ), then B ′ = p j=1 B j where B 1 , B 2 , . . . , B p are the connected components of B in G 1 linked to i. We get:

(30) v(B ∪ {i}) -v(B) = v   p j=1 B j ∪ {i}   -v(B 1 ) -v(B 2 ).
Then (30) and the superadditivity of (N, v) imply:

(31) v(B ∪ {i}) -v(B) ≥ v   p j=2 B j ∪ {i}   -v(B 2 ).
As (29) or ( 31) is satisfied, we get that (31) is always satisfied when i is linked to B 2 .

As e 1 / ∈ E(A) and e 1 / ∈ E(A ∪ {i}), we are in the same situation as in Case 2 for A and A ∪ {i}: P min (A) (resp. P min (A ∪ {i})) corresponds to the partition P M (A) (resp. P M (A ∪ {i})) into connected components in the graph G3 = (N, E 3 ). Therefore we have:

(32) v(A ∪ {i}) -v(A) = v M (A ∪ {i}) -v M (A)
where (N, v M ) is the Myerson's game associated with G3 . As 1 / ∈ A, there is no component of A containing vertex 1. Let A 1 be the component of A in G3 containing vertex 2. By Condition 2, we have A 1 = {2} and A 1 cannot be linked to i in G3 . Let à be the set of connected components of A in G3 linked to i. 26) is satisfied. Otherwise, let à = {A 2 , A 3 , . . . , A q } with q ≥ 2 be the set of connected components of A in G3 linked to i. Then we have:

If à = ∅, then v M (A ∪ {i}) -v M (A) = v(i) and (
(33) v M (A ∪ {i}) -v M (A) = v   q j=2 A j ∪ {i}   - q j=2 v(A j ).
Let us assume that two components in à are linked to 2 in G (by edges of weight σ 2 by Condition 2). We can suppose that these two components are A 2 and A 3 after renumbering if necessary. Then there exists a simple cycle C containing i, 2, and some vertices j 2 ∈ A 2 and j 3 ∈ A 3 as represented in Figure 44. By Condition 5, C is complete. Then {j 2 , j 3 } ∈ E(A) ∩ E 3 and

j 2 i 2 j 3 σ 3 σ 3 σ 3 σ 3 σ 2 σ 2 A 1 A 2 A 3 Figure 44: Cycle C.
links A 2 to A 3 in G3 , a contradiction. Hence, at most one component A 2 in à is linked to 2. By Condition 3, only A 2 can contain edges and the other potential components in à are singletons. Thus (33) reduces to:

(34) v M (A ∪ {i}) -v M (A) = v   q j=2 A j ∪ {i}   -v(A 2 ).
Following ( 31) and (34), it is sufficient to prove that the following inequality is satisfied to get (26):

(35) v   p j=2 B j ∪ {i}   -v(B 2 ) ≥ v   q j=2 A j ∪ {i}   -v(A 2 ),
or equivalently:

(36) v   p j=2 B j ∪ {i}   + v(A 2 ) ≥ v   q j=2 A j ∪ {i}   + v(B 2 ).
Each A j , with 3 ≤ j ≤ q, is a singleton A j = {k j } such that {2, k j } / ∈ E. By contradiction, let us assume k j ∈ B 2 . Then, as 2 ∈ B 2 and {2, k j } / ∈ E, there exists a vertex l 2 in B 2 such that the edge ẽ2 = {2, l 2 } belongs to E and an elementary path γ in B 2 linking l 2 to k j . By definition of k j , we

i 2 k 3 l 2 σ 3 σ 3 σ 3 σ 2 ẽ2 σ 2 A 1 A 3 B 2 Figure 45: Cycle C. have {i, k j } ∈ E 3 , but {2, k j } / ∈ E. Then Condition 3 implies {2, i} ∈ E. We obtain a simple cycle C in G 1 induced by {2, i} ∪ {i, k j } ∪ γ ∪ {l 2 , 2} as represented in Figure 45 for j = 3. Following Condition 5, C is complete. Hence {2, k j } ∈ E, a contradiction. Therefore k j /
∈ B 2 for all j, 3 ≤ j ≤ q. If A 2 ∩B 2 = ∅, then we have A 2 ⊆ B 2 and therefore ( q j=2 A j ∪{i})∩B 2 = A 2 . Then the supermodularity of v applied to q j=2 A j ∪ {i} and B 2 gives:

(37) v   q j=2 A j ∪ {i} ∪ B 2   + v(A 2 ) ≥ v   q j=2 A j ∪ {i}   + v(B 2 ).
Note that if A 2 ∩ B 2 = ∅, then A 2 is a singleton (otherwise by Condition 3 there is an edge linking A 2 to 2 and then A 2 belongs to B 2 ), and (37) is still satisfied as v(A 2 ) = 0 = v(∅). As p j=2 B j ∪ {i} is the connected component of B ∪ {i} in G 1 containing i, we have q j=2 A j ∪ {i} ∪ B 2 ⊆ p j=2 B j ∪ {i}, and the superadditivity of v implies:

(38) v   p j=2 B j ∪ {i}   ≥ v   q j=2 A j ∪ {i} ∪ B 2   .
Finally ( 38) and ( 37) imply (36) and therefore (26) is satisfied.

Case 4 Let us assume 2 / ∈ A and i = 2. Then E(A) ⊆ E(A ∪ {i} ⊆ E 3 , and P min (A) and P min (A ∪ {i}) are singleton partitions. Hence v(A∪{i})-v(A) = v(i) = 0 and as (N, v) is superadditive (cf. Corollary 2 page 4), ( 26) is satisfied.

Case 5 Let us assume i = 2. Then E(A) ⊆ E(B) ⊆ E 3 , and P min (A) and P min (B) are singletons partitions. Then v(A) = v(B) = 0 and ( 26) is equivalent to v(B ∪ {i}) ≥ v(A ∪ {i}). This last inequality is satisfied as (N, v) is superadditive (cf. Corollary 2 page 4).

Case 6 Let us assume i = 1 and 2 ∈ A. where A 1 , A 2 , . . . , A r (resp. B 1 , B 2 , . . . , B s ) are the connected components of A (resp. B) linked to 2 in G, i.e., for all j, 1 ≤ j ≤ r (resp. 1 ≤ j ≤ s), there exists k j ∈ A j (resp. l j ∈ B j ) such that ẽj = {2, k j } (resp. {2, l j }) belongs to E. Following Condition 3, the remaining components A r+1 , . . . , A p (resp. B s+1 , . . . , B q ) are necessarily singletons, i.e., A j = {k j } (resp. B j = {l j }), for all j, r + 1 ≤ j ≤ p (resp. s + 1 ≤ j ≤ q) for some vertex k j (resp. l j ) of G. For r + 1 ≤ j ≤ t (resp. s + 1 ≤ j ≤ u), A j (resp. B j ) is a singleton linked to vertex 1 (i.e., vertex i) by the edge {1, k j } (resp. {1, l j }) in G.

Claim 1. We can assume

(41) A j ⊆ B j , ∀j, 1 ≤ j ≤ r ≤ s,
after renumbering if necessary.

Proof of Claim 1. We assume that two components A 1 and A 2 are subsets of the same component B 1 . Let γ be a simple path in

B 1 linking k 1 ∈ A 1 to k 2 ∈ A 2 . Then {2, k 1 } ∪ γ ∪ {k 2 , 2} induces a cycle C in G 1 as represented in Figure 46. By Condition 5, C is complete. Hence the chord {k 1 , k 2 } ∈ E(A) ∩ E 3 and links A 1 to A 2 , a contradiction.
Claim 2. We can assume

(42) A r+j = B s+j , ∀j, 1 ≤ j ≤ t -r,
after renumbering if necessary, except in the two following situations:

k 2 σ 3 σ 3 σ 3 σ 3 σ 2 σ 2 A 1 A 2 B 1 Figure 46: Cycle C.
1. C3 exists and there exists a unique triangle C 3 adjacent to C3 and containing 1 but not e 1 . Assuming V ( C3 ) = {1, 2, 3} then 3 ∈ B \ A, C 3 = {1, A r+1 , 3, 1}, and we can assume

A r+1 ∈ B 1 or A r+1 ∈ B r+1 and A r+j = B s+j-1 , for all j, 2 ≤ j ≤ t -r. 2. C4 exists. Assuming V ( C4 ) = {1, 2, 3, 4} then 3 ∈ B \ A, A r+1 = {4}, C4 = {1, 2, 3, A r+1 , 1} and we can assume {3, A r+1 } ⊆ B 1 or {3, A r+1 } ⊆ B r+1 and A r+j = B s+j-1 , for all j, 2 ≤ j ≤ t -r.
Proof of Claim 2. By Condition 4, there exists at most one chordless cycle Cm with m = 3 or 4 containing e 1 . If m = 3 (resp. m = 4) we assume V ( Cm ) = {1, 2, 3} (resp. V ( Cm ) = {1, 2, 3, 4}) after renumbering if necessary and we have w({2, 3}) = σ 2 , and w({3, 1}) = σ 3 (resp. w({3, 4}) = w({4, 1}) = σ 3 ).

To prove (42), we assume by contradiction the existence of a pair (h, j) with r + 1 ≤ h ≤ t and 1 ≤ j ≤ s such that:

(43)

A h ∩ B j = ∅.

As r + 1 ≤ h ≤ t, A h is a singleton {k h } linked to 1 but not to 2 in G. Let us suppose by contradiction k h ∈ B j for an index j ∈ {1, . . . , s}. Let γ be a shortest path linking k h to l j in B j (we have k h = l j as A h is not linked to 2 whereas B j is linked to 2 in G by ẽj = {2, l j }). As all edges in γ have weight σ 3 , Condition 3 implies that we can always choose l j such that γ is reduced to the edge {k h , l j } as represented in Figure 47. Then {1, 2, l j , k h , 1} induces

2 1 k h l j σ 1 e 1 σ 2 σ 3 σ 3 σ 3 σ 3 σ 2 A h B j Figure 47: A h is not linked to 2 but B j is linked to 2 by ẽj = {2, l j }.
a cycle of length 4 containing e 1 . Note that {1, l j } may exist in G.

If {1, l j } exists in G, then Conditions 4 and 6 imply l j = 3 (i.e. C3 = {1, 2, l j }) and C3 is adjacent to the cycle induced by {1, k h , 3, 1}, as represented in Figure 48. As l j = 3 we have 3 ∈ B \ A. We can assume h = r + 1 after renumbering if necessary. We get A r+1 ⊆ B j for some j, with 1 ≤ j ≤ s. If 1 ≤ j ≤ r (resp. r + 1 ≤ j ≤ s), we can assume j = 1 (resp. j = r + 1) after renumbering if necessary (note that B 1 also contains A 1 by Claim 1).

1 l j k h σ 1 e 1 σ 3 σ 2 σ 3 σ 3 σ 3 σ 3 σ 2 C3 A h B j
If {1, l j } does not exist in G, then the 4-cycle {1, 2, l j , k h , 1} has no chord ({2, k h } does not exist in G as k h is not linked to 2). Then Condition 4 implies l j = 3 and k h = 4, (i.e. C4 = {1, 2, l j , k h , 1}) as represented in Figure 49. Then we have {3, 4} ⊆ B j . As l j = 3 we have 3 ∈ B \ A. We can assume h = r + 1 after renumbering if necessary. Then we have {3, A r+1 } ⊆ B j for some j, with 1 ≤ j ≤ s. If 1 ≤ j ≤ r (resp. r + 1 ≤ j ≤ s), we can assume j = 1 (resp. j = r + 1) after renumbering if necessary.

Finally, by Conditions 4 and 6 we cannot have a second pair (h, j) satisfying (43).

By Condition 4, there exists at most one chordless cycle Cm with m = 3 or 4 containing e 1 . We have to consider several subcases taking into account the possible existence of such a cycle Cm . If m = 3 (resp. m = 4) we assume V ( Cm ) = {1, 2, 3} (resp. V ( Cm ) = {1, 2, 3, 4}) after renumbering if necessary and we have w({2, 3}) = σ 2 , and w({3, 1}) = σ 3 (resp. w({3, 4}) = w({4, 1}) = σ 3 ). Case 6.1 We assume that there exists a chordless cycle Cm with m = 3 or m = 4 containing e 1 and that the vertex 3 (resp. the vertices 3 and 4) of C3 (resp. C4 ) belongs to A. As the two particular situations described in Claim 2 require 3 ∈ B \ A, (42) is necessarily satisfied, i.e., we have A r+j = B s+j for all j, 1 ≤ j ≤ tr. As e 1 ∈ E(A ∪ {i}), P min (A ∪ {i}) is obtained by deleting e 1 in E(A ∪ {i}) and corresponds to the partition P M (A∪{i}) in G 1 . Let A ′ 1 ∪{i} be the component of A∪{i} in G 1 containing i. Let us observe that (using Cm ) 1 and 2 are connected in G 1 . Then A ′ 1 ∪ {i} = r j=1 A j ∪ t j=r+1 A j ∪ {2} ∪ {i} where A r+1 , . . . , A t are the singletons A j = {k j } of P min (A) linked to 1 in G 1 but not linked to 2. If m = 3 (resp. m = 4) we can assume 3 in A 1 (resp. 3 and 4 in A 1 ), after renumbering if necessary, as represented in Figure 50 (resp. Figure 51) with r = 2, t = 3, and p = 4. Then each A j with 2 ≤ j ≤ r is connected to 2 by ẽj = {2, k j } for some k j ∈ A j and connected to 1 by the elementary path {1, {1, 3}, 3, {3, 2}, 2, ẽj , k j } (resp. {1, {1, 4}, 4, {4, 3}, 3, {3, 2}, 2, ẽj , k j }) in G 1 if m = 3 (resp. m = 4). We get P min (A ∪ {i}) = {A ′ 1 ∪ {i}, A t+1 , . . . , A p } where A j , t + 1 ≤ j ≤ p, are the singletons of P min (A) which are neither linked to 1 nor to 2. In the same way, we have P min (B ∪ {i}) = {B ′ 1 ∪ {i}, B u+1 , . . . , B q } with B ′ 1 = s j=1 B j ∪ u j=s+1 B j ∪{2}. As A j for j ≥ r +1 and B j for j ≥ s + 1 are singletons, we have: We can now prove Proposition 28.

Proof of Proposition 28.

1. Let us consider edges e 1 , e 2 , e 3 of weights σ 1 < σ 2 < σ 3 . By Theorem 27 we can assume e 1 = {1, 2}, e 2 = {2, 3}, and e 3 either incident to 3 or incident to 1. By contradiction, let us consider an edge e which is not connected to e 1 . If e 3 is incident to 3 (resp. to 1), then applying Lemma 29 at first to the couple of edges (e 1 , e 2 ) and then to the couple (e 2 , e 3 ) (resp. (e 1 , e 3 )) we get at first w(e) = σ 2 and then w(e) = σ 3 , a contradiction.

2. Let us now consider edges e 1 , e 2 , e 3 of weights w 1 = w 2 = σ 1 and w 3 = σ 2 . By Theorem 24 we can assume e 1 = {1, 2}, e 2 = {1, 3}, and e 3 incident to 3. By contradiction, let us consider an edge e which is not connected to e 1 . At first we apply Lemma 29 to the couple of edges (e 2 , e 3 ) so that we get w(e) = w 3 = σ 2 and then we apply Lemma 13 to the couple of edges (e 1 , e 2 ) (we have w(e) = σ 2 > σ 1 = w 1 = w 2 ), so that e has to be linked to 1 by an edge of weight σ 1 , a contradiction.

3. Let us now assume there are only two different weights and only one edge e 1 = {1, 2} of minimum weight σ 1 (in a connected component of G). Let us consider an edge e 2 = {2, 3} of weight w 2 = σ 2 > σ 1 adjacent to e 1 . Let us consider an edge e which is not connected to e 1 . At first we apply Lemma 29 to the couple of edges (e 1 , e 2 ) so that we get w(e) ≥ σ 2 . Let us assume by contradiction w(e) > σ 2 .

Then we apply Lemma 13 to the couple of edges (e 1 , e 2 ) (we have w(e) > σ 2 = max(w 1 , w 2 )), so that e has to be linked to 2 by an edge of weight σ 2 , a contradiction. Hence w(e) = σ 2 .

Remark 9. For a given weighted graph inheritance of convexity can be verified in polynomial time. By Theorem 27 (resp. 24) in the case of three 1 , e ′ 2 }) and if 2 ′ and 3 ′ are connected in this graph that either the edge {2 ′ , 3 ′ } ∈ E or that the vertices 1 ′ , 2 ′ , 3 ′ are connected to the same vertex 1 or 2 by an edge. The proof that it is sufficient can be made by induction on the size |C| of a cycle C with constant weight σ 2 .

Proposition 7 .

 7 Let G = (N, E, w) be a weighted graph. If for all ∅ = S ⊆ N , the P min -restricted game (N, u S ) is F-convex, then the Star and Path Conditions are satisfied. For a given cycle in G, C = {1, e 1 , 2, e 2 , . . . , m, e m , 1} with m ≥ 3, we denote by E(C) the set of edges {e 1 , e 2 , . . . , e m } of C and by Ê(C) the set composed of E(C) and of the chords of C in G.

  (b) C has at most one non-maximum weight chord, (c) C and C ′ have no maximum weight chord, (d) C and C ′ have no common chord, then C and C ′ cannot have two common non-maximum weight edges. Moreover C and C ′ have a unique common non-maximum weight edge e 1 if and only if there are non-maximum weight edges e 2 ∈ E(C) \ E(C ′ ) and e ′

Figure 2 :

 2 Figure 2: e ′ linking e to vertex 2.

Figure 5 :

 5 Figure 5: e ′′ = {2 ′ , 2 ′′ } linking e ′ to 2 ′ .

Figure 6 :

 6 Figure 6: e ′′ = {1 ′ , 2 ′ } linking e ′ to 2 ′ .

  ′ and v ′′ in N 1 . By definition v ′ and v ′′ are end-vertices of edges e ′ and e ′′ with w(e ′ ) = w(e ′′ ) = σ 1 . If e ′ = e ′′ or if e ′ and e ′′ are adjacent, then e ′ or e ′′ or e ′ ∪ e ′′ corresponds to a path in G N 1 linking v ′ to v ′′ . Otherwise, let γ be a shortest path in G linking e ′ to e ′′ . Then, the Path condition applied to γ ′ = e ′ ∪ γ ∪ e ′′ implies w(e) ≤ max(w(e ′ ), w(e ′′ )) = σ 1 and therefore w(e) = σ 1 for all edge e ∈ γ. Hence γ

Figure 7 :Figure 8 :

 78 Figure 7: e = {2, m}. condition applied to {e m-1 , e m , e} implies w m-1 = w m , a contradiction.Let us now assume e = {2, m + 1} as represented in Figure8. Then

  Figure10:w 1 = w 2 < w 3 = • • • = w m = M .

  Figure 11: w(e) < w 1 = w 2 < w 3 = w 4 = M . plied to the cycle {1, e 1 , 2, e, 5, {5, 4}, 4, e 4 , 1} implies w({4, 5}) = M > w(e). Hence we have either P min (A) = {{2}, {4, 5}} or P min (A) = {{2}, {4}, {5}}. Moreover P min (A ∪ {i}) = {{2, 3, 4}, {5}} or {A ∪ {i}}, and P min (B) = {{1, 2, 4}, {5}} or {B}. If P min (A ∪ {i}) = {{2, 3, 4}, {5}}, then taking A ′ = {2, 3, 4} we get P min (A) |A ′ = {{2}, {4}} = {2, 4} = P min (B) |A ′ and it contradicts Theorem 3. Otherwise taking A ′ = A ∪ {i}, we get

Figure 13 :Figure 14

 1314 Figure13:w 1 = σ 1 < w 2 = σ 2 < w 3 = σ 3 .

Figure 18

 18 Figure 18: γ ′ = {e} ∪ γ ∪ {e 1 , e 3 }.

  Figure 20: C4 .

Figure 21 :

 21 Figure 21: Edge-weights have only two values σ 1 < σ 2 .

Figure 23 :

 23 Figure 23: C 3 and C3 .

Figure 24 :

 24 Figure 24: C3 and two other triangles with common edge e 3 . remark that {2, j} and {2, k} cannot exist in E otherwise it contradicts the Adjacent Cycles condition), and P min (B) = {{2}, {3, j, k}}. Taking A ′ = {1, j, k} we get P min (A) |A ′ = {{j}, {k}} = {j, k} = P min (B) A ′ and it contradicts Theorem 3.

  Claims 3 and 4 in Lemma 23 are represented in Figures 25 to 28

  .

Figure 25 :

 25 Figure 25: Situation of Claim 3 in Lemma 23.

Figure 28 :

 28 Figure 28: Situation of Claim 4c in Lemma 23.

Figure 31 :

 31 Figure 31: C not linked by an edge to e 1 .

Figure 32 :

 32 Figure 32: Cycle C incident to 2. {{1 ′ , 4}, {2}}, P min (A ∪ {i}) = {{1 ′ }, {2, 3, 4}} or {A ∪ {i}}, and P min (B) = {{1 ′ }, V (C) \ {3}} or {B}. Then for any A ′ ∈ P min (A ∪ {i}) containing 2, we have {2} ∈ P min (A) |A ′ but {2} / ∈ P min (B) |A ′ and it contradicts Theorem 3. (If P min(A ∪ {i}) = {{1 ′ }, {2, 3, 4}} then taking A ′ = {2, 3, 4}, we get P min (A) |A ′ = {{2}, {4}} = {{2, 4}} = P min (B) |A ′ . If P min (A ∪ {i}) = {A ∪ {i}}, then taking A ′ = A ∪ {i}, we get P min (A) |A ′ = {{1 ′ }, {2}, {4}} or {{1 ′ , 4}, {2}} and P min (B) |A ′ = {{1 ′ }, {2, 4}} or {{1 ′ ,2, 4}}. Therefore we always have P min (A) |A ′ = P min (B) |A ′ , and it contradicts Theorem 3.) Hence we have e = {2, 4} ∈ E and w(e) = σ 2 , otherwise we have a contradiction with Star condition applied to {e, e 1 , e 2 }. Then we can consider the cycle {1, e 1 , 2, e, 4, e 4 , . . . , m, e m , 1} and by the same reasoning {2, 5} ∈ E. Iterating we get {2, j} ∈ Ê(C) for all j ∈ V (C) \ {2}.4. Let us consider E1 = {e ′ 1 } with e ′ 1 = {1 ′ , 2 ′ } and a cycle C = {1, e 1 ,2, e 2 , 3, . . . , m, e m , 1} with constant weight σ 2 or σ 3 and not incident to e 1 but linked to e 1 by an edge e = {2, 2 ′ } of weight σ 2 .If e ′ = {2 ′ , j} ∈ E for some j ∈ V (C) \ {2}, then we can consider the cycles C ′ = {2 ′ , e, 2, e 2 , 3, . . . , e j-1 , j, e ′ , 2 ′ } and C ′′ = {2 ′ , e ′ , j, e j , j + 1 . . . , e m , 1, e 1 , 2, e, 2 ′ } as represented in Figure33. Then C ′ and C ′′ are incident to e ′ 1 and Claim 3 (applied successively to C ′ and C ′′ ) implies that {2 ′ , k} ∈ E for all k ∈ V (C). Hence Claim 4b is satisfied.

Figure 33 :

 33 Figure 33: C ′ and C ′′ .

  and B = (V (C) \ {i}) ∪ A 2 as represented in Figure34. By

Figure 34 :

 34 Figure 34: C linked to e ′ 1 by an edge.

Figure 35 :

 35 Figure 35: C = {2, e ′ j , j, e j , j + 1, . . . , k, e ′ k , 2} and {1 ′ , j} ∈ E.

Figure 36 :

 36 Figure 36: e 1 adjacent to C m .

Figure 38 :

 38 Figure 38: C m with m = 5.

Figure 39 :

 39 Figure 39: C 4 and C3 = {1, e 1 , 2, e, 3 ′ , e ′ , 1}. e ′ 3 = {3 ′ , 4 ′ }, and e ′ 4 = {4 ′ , 1} the edges in E(C 4 ) and by e ′ = {1, 3 ′ } the chord of C 4 incident to 1. Both edges e ′2 and e ′ 3 have to be linked to node 2. But there can be only one edge e linking 2 to V (C 4 ) \ {1}, otherwise we get a contradiction to the cycles condition as with m ≥ 5. Hence we necessarily have e = {2, 3 ′ } as represented in Figure39. Then C3 = {1, e 1 , 2, e, 3 ′ , e ′ , 1} is a triangle containing edges with weights σ 1 < σ 2 < σ 3 , and {1, e ′ 1 , 2 ′ , e ′ 2 , 3 ′ , e ′ , 1} and {1, e ′ , 3 ′ , e ′ 3 , 4 ′ , e ′ 4 , 1} are two triangles adjacent to C3 containing the edge e ′ of weight σ 3 . It contradicts Lemma 22. Hence m = 3.C 3 = {1, e ′ 1 , 2 ′ , e ′ 2 , 3 ′ , e ′ 3 ,1} is a triangle with constant weight σ 3 and e ′ 2 is linked to 2 by an edge of weight σ 2 . There is only one edge e linking e ′ 2 to 2 otherwise it contradicts the Adjacent cycles condition as with m ≥ 5. We can assume w.l.o.g. e = {2, 2 ′ } as represented in Figure40. Hence the triangle C3 = {1, e 1 , 2, e, 2 ′ , e ′ 1 , 1} exists and

Figure 40 :

 40 Figure 40: C 3 and C3 = {1, e 1 , 2, e, 2 ′ , e 1 ′ , 1}.

6.

  If a cycle C m does not contain e 1 and if 1 ∈ V (C m ), then m = 3 and such a triangle is unique (if it exists) and is adjacent to a unique triangle C3 which contains the edge e 1 .Remark 7. Let us observe that Conditions 1 to 5 imply that the graphG 1 = (N, E \ {e 1 }) is cycle-complete. Indeed using Condition 5 a cycle C m of G 1 is a complete cycle in G.By contradiction, let us assume that e 1 is a chord of C m . Then we can build two adjacent cycles C ′ m and C ′′ m with common edge e 1 . Using Conditions 2 and 3 we can replace (if necessary) C ′ m and C ′′ m by two chordless cycles C ′ and C ′′ (with e 1 as common edge) of length at most 4. It contradicts Condition 4. Remark 8. Adjacent cycles condition and Pan condition are straightforward consequences of Conditions 1 to 5 in Theorem 27.

Case 3

 3 Let us assume 2 ∈ A, and 1 ∈ B \ A. Then i / ∈ {1, 2} and e 1 / ∈ E(A) but e 1 ∈ E(B). As e 1 ∈ E(B), we are in the same situation as in Case 1 for B and B ∪ {i}: we delete e 1 to get P min (B) and P min (B ∪ {i}). Then v(B) = v M (B) and v(B ∪ {i}) = v M (B ∪ {i}) where (N, v M ) is the Myerson's game associated with G 1 = (N, E \ {e 1 }).

Figure 48 :

 48 Figure 48: l j = 3 and C3 adjacent to the cycle induced by {1, k h , 3, 1}.

Figure 49 :

 49 Figure 49: l j = 3 and k h = 4.

Figure 50 :

 50 Figure 50: C3 and A 1 , A 2 linked to 2, A 3 linked to 1.

Figure 51 :

 51 Figure 51: C4 and A 1 , A 2 linked to 2, A 3 linked to 1.

Figure 52 :

 52 Figure 52: w 1 < w 2 and w(e) < w 2 .

  different edge-weights (resp. two different edge-weights with at least two edges of minimal weight), we have to verify the cycle-completeness condition as for Myerson game. More precisely, for two adjacent edges e 1 = {1, 2}, e 2 = {1, 3} we have to see if the vertices 2 and 3 are connected in the graph (N, E \ {e 1 , e 2 }) and if 2 and 3 are connected in this graph that {2, 3} ∈ E. Now by Theorem 25 in the case of two different weights and only one edge e 1 = {1, 2} of minimum weight σ 1 , for each couple of adjacent edges e ′ 1 = {1 ′ , 2 ′ }, e ′ 2 = {1 ′ , 3 ′ } both of weight σ 2 , we have to see if the vertices 2 ′ and 3 ′ are connected in the graph (N, E \ {e 1 , e ′

  there is also a component B ′ of P min (B) containing A 2 . Then P min (B) |A ′ ∩A = P min (A) |A ′ ∩A as P min (A) corresponds to a singleton partition but B ′ ∩ A ′ contains A 2 . It contradicts Theorem 3 applied with F = 2 N \{∅}. Therefore there exists an edge e ′ linking e to 2. If e ′ = e 1 and e 2 , then Star condition applied to {e 1 , e 2 , e ′ } implies w(e ′ ) = w 1 if w 2 < w 1 , w(e ′ ) = w 2 if w 1 < w 2 , and w(e ′ ) ≤ w 1 = w 2 otherwise.

	We give in Figures 2 and 3 examples of graphs satisfying the necessary
	condition established in Lemma 13.

  Hence there exists an edge e ′′ ∈ E linking e ′ to 2 ′ (e ′′ can coincide with e).

	We can assume w 1 ≤ w 2 . By contradiction, let us assume w(e) < w(e ′ ). Applying Lemma 13 to e (resp. e ′ ), there exists an edge e ′ 2 (resp. e ′′ 2 ) linking e (resp. e ′ ) to 2 such that w ′ 2 ≤ max(w 1 , w 2 ) < w(e) (resp. w ′′ 2 ≤ max(w 1 , w 2 ) < w(e ′ )) (e ′ 2 (resp. e ′′ 2 ) may coincide with e 1 or e 2 ). We set e ′ 2 = {2, 2 ′ } (resp. e ′′ 2 = {2, 2 ′′ }) where 2 ′ (resp. 2 ′′ ) is an end-vertex of e (resp. e ′ ) as represented in Figure 4. If 2 ′ = 2 ′′ , then e ′ 2 = e ′′ 2 and as
	e	2 ′		2 ′′	e ′
		e ′ 2		e ′′ 2
	1	e 1	2	e 2	3
	Figure 4: w ′ 2 ≤ max(w 1 , w 2 ) < w(e) and w ′′ 2 ≤ max(w 1 , w 2 ) < w(e ′ ).
	w ′ 2 < w(e) < w(e ′ ) we get a contradiction with Star condition applied to {e ′ 2 , e, e ′ }. Otherwise, as w ′ 2 < w(e) < w(e ′ ) we can still apply Lemma 13 to e ′ and the pair of adjacent edges {e ′ 2 , e}.

  and if there exists a cycle C with constant weight σ 2 , then there are only two different edge-weights (σ 2 = σ 3 ). Moreover, if C is not incident to e 1 and not linked to e 1 by an edge, then C is complete.

3. If |E 1 | = 1 with E 1 = {e 1 } and e 1 = {1, 2}, then for every cycle C with constant weight σ 2 or σ 3 and incident to 2 (resp. to 1), {2, j} ∈ E(C)

  Then e 1 / ∈ E(A) and e 1 / ∈ E(B) but e 1 ∈ E(A∪{i}) and e 1 ∈ E(B ∪{i}). As e 1 / ∈ E(A) (resp. e 1 / ∈ E(B)), we are in the same situation as in Case 2 for A (resp. B): P min (A) (resp. P min (B)) corresponds to the partition P M (A) (resp. P M (B)) into connected components in the graph G3 = (N, E 3 ). {{2}, A 1 , A 2 , . . . , A r , A r+1 , . . . , A t , A t+1 , . . . , A p }

		Let
	us set:
	(39) P M (A) = and
	(40)	P

M (B) = {{2}, B 1 , B 2 , . . . , B s , B s+1 , . . . , B u , B u+1 , . . . , B q }

Documents de travail du Centre d'Economie de la Sorbonne -2017.51

F is weakly union-closed if A ∪ B ∈ F for all A, B ∈ F such that A ∩ B = ∅ (Faigleet al.,

2010). Weakly union-closed families were introduced and analysed in[START_REF] Algaba | Extensión de juegos definidos en sistemas de conjuntos[END_REF][START_REF] Algaba | The position value for union stable systems[END_REF] and called union stable systems. 4 Documents de travail du Centre d'Economie de la Sorbonne -2017.51

As A ′ 1 ⊆ B ′ 1 , the convexity of (N, v) implies:

). We will prove:

(48) can also be written:

Let us define:

(50)

By the superadditivity of v, we obtain:

which is equivalent to:

By (51), to obtain (48) or (49), it is enough to prove:

which is equivalent to:

As (N, v) is a convex game, we can apply Lemma 4 to

By Claims 1 and 2 we have A ′ 1 ∩ B j = A j for all j, 1 ≤ j ≤ r, and

Finally, Claims 1 and 2 also imply r j=1 A j ⊆ r j=1 B j and t j=r+1 A j ⊆ s+t-r j=s+1 B j . Therefore we have A ′ 1 ⊆ B ′′ 1 , and ( 54) is equivalent to (52).

Case 6.2

We now assume that there exists a cycle Cm with m = 3 or m = 4 and that the vertex 3 (resp. either 3 or 4) of C3 (resp. C4 ) belongs to B \ A. Moreover, if m = 4 we assume 3 and 4 in B. We recall that A ′ 1 ∪ {i} denotes the component of P min (A ∪ {i}) containing i. Now we have A ′ 1 = t j=r+1 A j where A r+1 , . . . , A t are the singletons of P min (A) linked to 1 but not to 2. Note that if we have 4 ∈ A and 3 ∈ B \ A, then 4 corresponds to one of the A j with r + 1 ≤ j ≤ t and therefore belongs to

. . , A p } and this implies:

As 3 (resp. 3 and 4) belong to B if m = 3 (resp. m = 4), we have P min (B ∪ {i}) = {B ′ 1 ∪ {i}, B u+1 , . . . , B q } with B ′ 1 = s j=1 B j ∪ u j=s+1 B j ∪ {2} as in Case 6.1. Hence we have:

By ( 55) and (56), we have to prove:

We have to consider subcases. Subcase 6.2.1

We first assume (42) satisfied in Claim 2, i.e., we have

The superadditivity of (N, v) implies:

which is equivalent to:

Hence to prove (57) it is enough to prove:

By ( 42) we have t j=r+1 v(A j ) = s+t-r j=s+1 v(B j ). Therefore ( 61) is equivalent to:

As (N, v) is a convex game, we can apply Lemma 4 to A ′ 2 ∪ {2}, B ′ 2 , and the partition {B 1 , B 2 , . . . , B s } of B ′ 2 to get:

By Claim 1, we have A j ⊆ B j , for all j, 1 ≤ j ≤ r ≤ s. Therefore, we have

Then (63) implies (62). In the next subcases we assume (42) not satisfied, i.e., we are in one of the two specific situations described in Claim 2. Subcase 6.2.2 Let us assume A r+1 ∈ B 1 . We have A r+j = B s+j-1 for all j, 2 ≤ j ≤ tr.

Let us recall we have:

Applying Lemma 4 to à ∪ {i}, B ′ 1 , and the partition {{2}, B 1 , . . . , B s , B s+1 , . . . , B u } of B ′ 1 we get:

By Claim 1 we have A j ⊆ B j for all j, 1 ≤ j ≤ r ≤ s. As A r+1 ∈ B 1 and

Note that any A j-s+r+1 with s + 1 ≤ j ≤ s + tr -1 corresponds to a singleton. Hence (66) becomes:

From ( 64) and ( 67) we obtain:

We set

Then ( 68) and (69) imply:

, the convexity of (N, v) also implies:

Then ( 70) and (71) imply: As A r+1 is a singleton, we have v(A r+1 ) = 0. ( 72) and (73) imply:

As A 1 ⊆ A ′ 2 and as A r+1 ∩ (A ′ 2 ∪ {2}) = ∅, the convexity of (N, v) implies:

( 74) and ( 75) imply:

Using (55), we obtain:

Subcase 6.2.3

We now assume A r+1 ∈ B r+1 . As in the previous case, setting

We set:

(79) Ã :=

Applying Lemma 4 to à ∪ {i}, B ′ 1 , and the partition {{2}, B 1 , . . . , B s , B s+1 , . . . , B u } of B ′ 1 we get:

By Claim 1 we have A j ⊆ B j for all j, 1 ≤ j ≤ r ≤ s. As A r+1 ∈ B r+1 and A r+j = B s+j-1 for all j, 2 ≤ j ≤ tr, we get à ∩ B j = A j for all j, 1 ≤ j ≤ r +1, Ã∩B j = ∅ for all j, r +2 ≤ j ≤ s, Ã∩B j = A j-s+r+1 for all j, s + 1 ≤ j ≤ s + tr -1, and à ∩ B j = ∅ for s + tr ≤ j ≤ u. Moreover, we have à ⊆ B ′ 1 . Note that any A j-s+r+1 with s ≤ j ≤ s + tr -1 corresponds to a singleton. Hence (80) becomes:

From ( 78) and ( 81) we obtain:

We set 82) and the superadditivity of (N, v) imply:

Using (55), we obtain:

Subcase 6.3

We assume either the non-existence of a chordless cycle Cm with m = 3 or m = 4 containing e 1 or the existence of such a cycle but in this last case we assume that the vertex 3 (resp. 3 or 4) of C3 (resp. of C4 ) does not belong to B. As the two particular situations described in Claim 2 require the existence of C3 or C4 and 3 ∈ B \ A, (42) is necessarily satisfied, i.e., we have A r+j = B s+j for all j, 1 ≤ j ≤ tr. As in Case 6.2, we have

A j , and therefore (55) is still valid:

Similarly, for B we have P min (B ∪ {i}) = {B ′ 1 ∪ {i}, B ′ 2 ∪ {2}, B u+1 , . . . , B q } with B ′ 1 = u j=s+1 B j and B ′ 2 = s j=1 B j , and therefore:

We have to prove:

As A ′ 1 ⊆ B ′ 1 the superadditivity of (N, v) implies:

Applying Lemma 4 to A ′ 2 ∪ {2}, B ′ 2 , and the partition {B 1 , B 2 , . . . , B s } of B ′ 2 , we get:

By Claim 1 we have A j ⊆ B j for all j, 1 ≤ j ≤ r ≤ s. As A r+j = B s+j for all j, 1 ≤ j ≤ tr, we get A ′ 2 ∩ B j = A j for all j, 1 ≤ j ≤ r and A ′ 2 ∩ B j = ∅ for all j, r + 1 ≤ j ≤ s. Moreover, we have A ′ 2 ⊆ B ′ 2 . Hence (89) becomes:

Adding ( 88) and ( 90), we obtain (87).

Disconnected graphs

We finally consider the case of disconnected weighted graphs. We prove that if there is inheritance of convexity for P min then the underlying graph G has to be connected or has only one component with non constant weight.

Proposition 28. Let G = (N, E, w) be a weighted graph and let us assume that for all ∅ = S ⊆ N the P min -restricted game (N, u S ) is convex.

1. If G has a connected component with three different weights σ 1 < σ 2 < σ 3 , then all other connected components of G are singletons.

2. If G has a connected component with two different weights σ 1 < σ 2 and at least two edges of minimum weight σ 1 , then all other connected components of G are singletons.

3. If G has a connected component with two different weights σ 1 < σ 2 and only one edge of minimum weight σ 1 , then all other connected components of G have constant weight σ 2 or are singletons.

To prove Proposition 28 we need the following lemma.

Lemma 29. Let G = (N, E, w) be a weighted graph and let us assume that for all ∅ = S ⊆ N the P min -restricted game (N, u S ) is convex. Let e 1 = {1, 2} and e 2 = {2, 3} be two adjacent edges such that w 1 < w 2 and let e be an edge which is not incident to 1. Then we have w(e) ≥ w 2 and if moreover e is not linked to 2 by an edge, then w(e) = w 2 .

Proof. We set e = {j, k}. If e is incident to 2, Star condition implies w(e) = w 2 . If e is incident to 3, Path condition implies w(e) ≥ w 2 . Hence we can assume that e is not incident to the vertices 1, 2, and 3. By contradiction, let us assume w(e) < w 2 . Let us consider i = 1 and the subsets A = {2, 3} and