FIRST SUPPLEMENT TO THE PURCHASE CONTRACT AGREEMENT AMONG

Exhibit 4.10

FIRST SUPPLEMENT

TO THE

PURCHASE CONTRACT AGREEMENT

AMONG

ALBERTSON’S, INC.,

NEW ALBERTSON’S, INC.

AND

U.S. BANK TRUST NATIONAL ASSOCIATION,

AS PURCHASE CONTRACT AGENT

THIS FIRST SUPPLEMENT TO THE PURCHASE CONTRACT AGREEMENT, dated as of June 1, 2006 (this “Supplemental Agreement”), among Albertson’s, Inc., a Delaware corporation (the “Company”), New Albertson’s, Inc., a Delaware corporation formerly known as New Aloha Corporation (“New Albertson’s”), and U.S. Bank Trust National Association, acting as purchase contract agent for the Holders of Units from time to time (the “Agent”) pursuant to the Purchase Contract Agreement (as hereafter referred to).

WHEREAS, the Company and the Agent executed and delivered a Purchase Contract Agreement, dated as of May 7, 2004 (the “Purchase Contract Agreement”), to provide for the execution and delivery of the Purchase Contracts and Certificates related to the Corporate Units and the Treasury Units (collectively, the “Units”);

WHEREAS, the Company and New Albertson’s are parties to that Agreement and Plan of Merger, dated as of January 22, 2006, by and between SUPERVALU INC., Emerald Acquisition Sub, Inc., the Company, New Albertson’s, and New Diamond Sub, Inc. (the “Merger Agreement”);

WHEREAS, pursuant to the terms of the Merger Agreement, New Diamond Sub, Inc., a wholly-owned subsidiary of New Albertson’s, shall merge with and into the Company with the Company being the surviving corporation (the “Diamond Merger”);

WHEREAS, the Merger Agreement provides that, at the effective time of the Diamond Merger (the “Initial Effective Time”), each share of Common Stock (or fraction of a share) of the Company issued and outstanding immediately prior to the Initial Effective Time (except for shares cancelled pursuant to Section 3.1(b) of the Merger Agreement and Dissenting Shares (as defined in the Merger Agreement)) will be converted into, and will be cancelled in exchange for, the right to receive one share of common stock (or an equal fraction of a share, if applicable) of New Albertson’s, par value $0.01 per share (“New Albertson’s Common Stock”);

WHEREAS, Section 9.01 of the Purchase Contract Agreement permits the Company to merge with another corporation provided certain terms and conditions are satisfied;

WHEREAS, the Diamond Merger results in the occurrence of a Reorganization Event;

WHEREAS, Section 5.04(b)(i) of the Purchase Contract Agreement provides that in the event of a Reorganization Event the Person formed thereby shall execute and deliver to the Agent an agreement supplemental to the Purchase Contract Agreement providing that each Holder of each Outstanding Unit shall have the rights provided by Section 5.04(b)(i) of the Purchase Contract Agreement and for adjustments for subsequent events that are as nearly equivalent as may be practicable to the adjustments provided for in Section 5.04(b)(i) of the Purchase Contract Agreement;

WHEREAS, Section 8.01 of the Purchase Contract Agreement authorizes the Company and the Agent to enter into a supplemental agreement without the consent of any Holders to, among other things, make provision with respect to the rights of Holders pursuant to the requirements of Section 5.04(b) of the Purchase Contract Agreement;

WHEREAS, the Company and New Albertson’s have requested that the Agent execute and deliver this Supplemental Agreement; and

NOW THEREFORE, in consideration of their mutual promises, New Albertson’s and the Company covenant and agree with the Agent as follows:

ARTICLE I

DEFINITIONS

Section 1.1 Definition of Terms. Unless the context otherwise requires:

(a) a term defined in the Purchase Contract Agreement has the same meaning when used in this Supplemental Agreement;

(b) a term defined anywhere in this Supplemental Agreement has the same meaning throughout;

(c) the singular includes the plural and vice versa; and

(d) headings are for convenience of reference only and do not affect interpretation.

ARTICLE II

CONCERNING THE DIAMOND MERGER

Section 2.1 New Albertson’s as Issuer of Common Stock upon Settlement.

(a) From and after the Initial Effective Time, the Company shall cause New Albertson’s to issue and deliver, and New Albertson’s agrees to so issue and deliver, the number of shares of New Albertson’s Common Stock which is sufficient to settle the Purchase Contracts as provided in Article III of this Supplemental Agreement, against payment in full of the Purchase Price in the manner set forth in the Purchase Contract Agreement and Section 2.1(b) hereof.

(b) The Company hereby agrees that it will immediately forward to New Albertson’s all funds received by it under Sections 5.02, 5.04(b)(ii), 5.07 or otherwise under the Purchase Contract Agreement for payment of the Purchase Price upon settlement of each Purchase Contract for the shares of New Albertson’s Common Stock to be so issued.

(c) Subject to the other provisions of this Supplemental Agreement, from and after the Initial Effective Time, references to the Common Stock shall relate to New Albertson’s Common Stock by operation of Section 5.04(b)(i) of the Purchase Contract Agreement, except to the extent that such reference is a reference to the Common Stock as of a time preceding the Initial Effective Time.

(d) Subject to the other provisions of this Supplemental Agreement, from and after the Initial Effective Time, any reference in the Purchase Contract Agreement to the “Company” shall be deemed to be a reference to New Albertson’s, and all covenants of the Company shall be deemed to be covenants of New Albertson’s, in each case to the extent necessary to give effect to Section 5.04(b) of the Purchase Contract Agreement and this Supplemental Agreement;

Section 2.2 Acceptance by Agent. The Agent accepts this Supplemental Agreement and agrees to execute its duties and responsibilities as hereby supplemented upon the terms and conditions set forth in the Purchase Contract Agreement, including without limitation the terms and provisions defining and limiting the liabilities and responsibilities of the Agent, which terms and provisions shall in like manner define and limit its liabilities and responsibilities in the performance of its duties created by the Purchase Contract Agreement as hereby supplemented; and without limiting the generality of the foregoing, the Company affirms its rights and responsibilities with respect to the Agent under Section 7.07(c) of the Purchase Contract Agreement.

ARTICLE III

CONCERNING SETTLEMENT

Section 3.1 Purchase Contract Settlement. The Company and New Albertson’s understand and agree that, pursuant to Section 5.04(b)(i) of the Purchase Contract Agreement, the Diamond Merger constitutes a Reorganization Event as a result of which as of the Initial Effective Time the Settlement Rate was adjusted such that each Holder of Units will receive:

(i) on the Purchase Contract Settlement Date with respect to each Purchase Contract forming a part thereof the number of shares of New Albertson’s Common Stock (without any interest thereon, and without any right to dividends or distribution thereon which have a record date that is prior to the Purchase Contract Settlement Date) equal to the number of shares of the Company’s Common Stock that would have been issuable on account of each Purchase Contract on the Purchase Contract Settlement Date if (A) the Diamond Merger had not occurred and this Supplemental Agreement not been entered into and (B) the New Albertson’s Common Stock were deemed to be the Company’s Common Stock for the purposes of all references in the Purchase Contract Agreement to the Company’s Common Stock (including, for the avoidance of doubt, in the computation of Adjusted Applicable Market Value) pertaining to a time after the Initial Effective Time,

(ii) on any Cash Merger Early Settlement Date with respect to any Cash Merger (such terms’ definitions as modified pursuant to Section 3.1(c)), the kind and amount of cash, securities and other property equal to the kind and amount of cash, securities and other property that would have been issuable on account of each Purchase Contract on such Cash Merger Early Settlement Date if (A) the Diamond Merger had not occurred and this Supplemental Agreement not been entered into, (B) the merger or consolidation of New Albertson’s constituting such Cash Merger were deemed to be a merger or consolidation of the Company, (C) the kind and amount of securities, cash and

other property receivable upon such Cash Merger by holders of New Albertson’s Common Stock were deemed to be the kind and amount of securities, cash and other property receivable upon such Cash Merger by holders of the Company’s Common Stock, and (D) the New Albertson’s Common Stock were deemed to be the Company’s Common Stock for the purposes of all references in the Purchase Contract Agreement to the Company’s Common Stock (including, for the avoidance of doubt, in the computation of Adjusted Applicable Market Value) pertaining to a time after the Initial Effective Time, or

(iii) on any Early Settlement Date with respect to each Purchase Contract forming a part thereof the number of shares of New Albertson’s Common Stock (without any interest thereon, and without any right to dividends or distribution thereon which have a record date that is prior to the Early Settlement Date) equal to the number of shares of the Company’s Common Stock that would have been issuable on account of each Purchase Contract if (A) the Diamond Merger had not occurred and this Supplemental Agreement not been entered into and (B) the New Albertson’s Common Stock were deemed to be the Company’s Common Stock for the purposes of all references in the Purchase Contract Agreement to the Company’s Common Stock (including, for the avoidance of doubt, in the computation of Adjusted Applicable Market Value) pertaining to a time after the Initial Effective Time,

subject in the case of each clause (i), (ii) and (iii) to any further adjustments in the Settlement Rate under Article V of the Purchase Contract Agreement prior to settlement, deeming all references to the Company’s Common Stock pertaining to a time after the Initial Effective Time to be references to the New Albertson’s Common Stock, and deeming all references to the Company pertaining to a time after the Initial Effective Time to be references to New Albertson’s. The Company shall, within 10 Business Days following the Diamond Merger, (a) deliver to the Agent an Officers’ Certificate pursuant to Section 5.05(a)(i) of the Purchase Contract Agreement, which shall set forth the method of calculation of the Settlement Rate as of the Initial Effective Time, as adjusted for the Diamond Merger, and (b) provide a written notice to the Holders of the Units, pursuant to Section 5.05(a)(ii) of the Purchase Contract Agreement.

Section 3.2 Rights of Holders. Each Holder of an Outstanding Unit shall have the rights provided by Section 5.04(b)(i) of the Purchase Contract Agreement.

Section 3.3 Further Adjustments. In accordance with the last paragraph of Section 5.04(b)(i) of the Purchase Contract Agreement, the Settlement Rate shall be adjusted for events subsequent to the Initial Effective Time, in a manner that is as nearly equivalent as may be practicable to the adjustments provided for in Section 5.04 of the Purchase Contract Agreement, as if New Albertson’s were the original “Company” and New Albertson’s Common Stock were the original “Common Stock” under the provisions of Section 5.04 of the Purchase Contract Agreement.

ARTICLE IV

MISCELLANEOUS

Section 4.1 Ratification of Purchase Contract Agreement. The Purchase Contract Agreement, as supplemented by this Supplemental Agreement, is in all respects ratified and confirmed, and this Supplemental Agreement shall be deemed part of the Purchase Contract Agreement in the manner and to the extent herein and therein provided.

Section 4.2 Effectiveness. This Supplemental Agreement shall become a legally effective and binding instrument upon the execution and delivery hereof by all parties hereto.

Section 4.3 Purchase Contract Agreement. Except as supplemented hereby, all provisions in the Purchase Contract Agreement shall remain in full force and effect.

Section 4.4 Third Party Rights. Nothing in this Supplemental Agreement or the Units, express or implied, shall give to any Person, other than the parties hereto and thereto and their successors hereunder and thereunder and the Holders of the Units, any benefit of any legal or equitable right, remedy or claim under the Purchase Contract Agreement, this Supplemental Agreement or the Units.

Section 4.5 Successors. All agreements of the Company and New Albertson’s in this Supplemental Agreement shall bind their respective successors and assigns, whether so expressed or not.

Section 4.6 Recitals. The recitals and statements herein contained are made by the Company and New Albertson’s and not by the Agent, and the Agent assumes no responsibility for the correctness thereof. The Agent makes no representations as to the validity or sufficiency of this Supplemental Agreement.

Section 4.7 Units Deemed Conformed. As of the Initial Effective Time, the provisions of each Unit then outstanding shall be deemed to be conformed, without the necessity for any reissuance or exchange of such Unit or any other action on the part of the Holders, New Albertson’s, the Company or Agent, so as to reflect this Supplemental Agreement.

Section 4.8 Governing Law. This Supplemental Agreement and the rights and obligations of the parties hereunder shall be governed by and construed in accordance with the laws of the State of New York.

Section 4.9 Separability. If any one or more of the provisions contained in this Supplemental Agreement or in the Units shall for any reason be held to be invalid, illegal or unenforceable in any respect, such invalidity, illegality or unenforceability shall not affect any other provisions of this Supplemental Agreement or of the Units, but this Supplemental Agreement and the Units shall be construed as if such invalid or illegal or unenforceable provision had never been contained herein or therein.

Section 4.10 Counterparts. This Supplemental Agreement may be executed in any number of counterparts, all of which taken together shall constitute one and the same instrument.

[SIGNATURE PAGES FOLLOW]

IN WITNESS WHEREOF, this First Supplement to the Purchase Contract Agreement is executed as of the date first set forth above.