Exhibit 1.01

Execution Version

17,869,565 Units

VALERO GP HOLDINGS, LLC

Representing Limited Liability Company Interests

UNDERWRITING AGREEMENT

December 18, 2006

LEHMAN BROTHERS INC.

UBS SECURITIES LLC

CITIGROUP GLOBAL MARKETS INC.

MORGAN STANLEY & CO. INCORPORATED

As Representatives of the several

Underwriters named in Schedule II attached hereto,

c/o Lehman Brothers Inc.

745 Seventh Avenue

New York, New York 10019

Ladies and Gentlemen:

Certain unitholders of Valero GP Holdings, LLC, a Delaware limited liability company (the “ Company ”), named in Schedule I hereto (the “ Selling Unitholders ”) propose to sell an aggregate of 17,869,565 units (the “ Firm Units ”), representing limited liability company interests in the Company (the “ Units ”).  In addition, Diamond Shamrock Refining and Marketing Company, a Delaware corporation and one of the Selling Unitholders (“ DSRMC ”), proposes to grant to the underwriters (the “ Underwriters ”) named in Schedule II attached to this agreement (this “ Agreement ”) an option to purchase up to an aggregate of 2,680,435 additional Units on the terms and for the purposes set forth in Section 3 (the “ Option Units ”).  The Firm Units and the Option Units, if purchased, are hereinafter collectively called the “ Offered Units .”

This is to confirm the agreement among the Company, the Selling Unitholders, Valero Energy Corporation, a Delaware corporation (“ Valero Energy ” and, together with the Selling Unitholders, the “ Selling Unitholder Parties ”), and the Underwriters concerning the purchase of the Offered Units from the Selling Unitholders by the Underwriters.

A.                                    It is understood and agreed to by all parties hereto that the Company owns, as of each Delivery Date (as defined in Section 4 hereof):

(i)                                      a 2% general partner interest in Valero L.P., a publicly traded Delaware limited partnership (the “ Partnership ”), held indirectly through a 100% indirect ownership interest in Riverwalk Logistics, L.P., a Delaware limited partnership and the general partner of the Partnership (the “ General Partner ”);

(ii)                                   10,213,894 common units representing a 21.38% interest in the Partnership, held indirectly through a 100% ownership interest in Riverwalk Holdings, LLC, a Delaware limited liability company (“ Riverwalk Holdings ”);

1

(iii)                                6,976 common units representing a 0.02% interest in the Partnership held indirectly through a 100% ownership interest in Valero GP, LLC, a Delaware limited liability company and the general partner of the General Partner (“ Valero GP ”); and

(iv)                               all of the incentive distribution rights in the Partnership (the “ Incentive Distribution Rights ”), held indirectly through a 100% ownership interest in the General Partner;

each as more particularly described in the Preliminary Prospectus and the Prospectus (as such terms are hereinafter defined).

B.                                      It is further understood and agreed to by all parties hereto that as of the date hereof:

(i)                                      Valero Energy owns 59.4% of the Units in the Company, indirectly held through its 100% ownership interest in the subsidiaries named in Schedule III hereto (each such entity listed on Schedule III a “ Valero Energy Subsidiary ,” and collectively the “ Valero Energy Subsidiaries ”) and shall ultimately receive the proceeds from the sale of the Offered Units as contemplated by this Agreement;

(ii)                                   The Partnership owns:

(a)                                   a 99.99% limited partner interest in Valero Logistics Operations, L.P., a Delaware limited partnership (“ Valero OLP ”);

(b)                                  a 0.01% general partner interest in Valero OLP, indirectly held through its 100% ownership interest in Valero GP, Inc., a Delaware corporation and general partner of Valero OLP (“ Valero OLP GP ” and, together with Valero OLP, the “ Valero OLP Entities ”);

(c)                                   a 99% limited partner interest in Kaneb Pipe Line Partners, L.P., a Delaware limited partnership (“ KPP ”);

(d)                                  a 1% general partner interest in KPP, indirectly held through a 100% indirect ownership interest in Kaneb GP, as hereinafter defined;

(e)                                   a 100% membership interest in Kaneb Pipe Line Company, LLC, a Delaware limited liability company (“ Kaneb GP ”) and the general partner of KPP and KPOP, as hereinafter defined, held indirectly through a 100% membership interest in Kaneb Services, LLC, a Delaware limited liability company and sole member of Kaneb GP (“ Kaneb Services ”);

(f)                                     a 100% ownership interest in Kaneb Pipe Line Operating Partnership, L.P., a Delaware limited partnership (“ KPOP ” and, together

2

with KPP, Kaneb GP and Kaneb Services, the “ Kaneb OLP Entities ”), held indirectly through KPP and Kaneb GP; and

(g)                                  a 100% ownership interest in each of the subsidiaries listed on Schedule IV hereto, except as otherwise indicated on Schedule IV (collectively, the “ Operating Subsidiaries ” and each individually an “ Operating Subsidiary ”), held, directly or indirectly, through either of Valero OLP or KPOP.

Valero GP, Riverwalk Holdings, the Partnership, the General Partner, the Valero OLP Entities and the Kaneb OLP Entities are collectively referred to herein as the “ Valero MLP Parties .”

C.                                      Prior to the execution hereof:

(i)                                      Valero OLP and the Partnership entered into the Fourth Amendment to the 5-Year Revolving Credit Agreement with JPMorgan Chase Bank, N.A., as Administrative Agent and the Lenders party thereto, dated as of November 30, 2006 (the “ Amended Credit Facility ”).

D.                                     It is further understood and agreed to by the parties hereto that the following additional transactions will occur substantially contemporaneously with the Initial Delivery Date (as defined in Section 4 hereof):

(i)                                      DSRMC, Valero Corporate Services Company, the Partnership, Valero OLP, the General Partner and Valero GP shall have entered into a Fourth Amended and Restated Services Agreement (the “ Amended Services Agreement ”) to conform to the description thereof set forth in the Prospectus under the caption “Certain Relationships and Related Transactions—Valero L.P.’s Relationship with Valero Energy.”

The “ Transaction Documents ” shall mean the Amended Credit Facility and the Amended Services Agreement.  The “ MLP Organizational Documents ” shall mean the Valero GP LLC Agreement, the Riverwalk Holdings LLC Agreement, the GP Partnership Agreement, the Partnership Agreement, the Valero OLP Partnership Agreement, the Kaneb Services LLC Agreement, the Kaneb GP LLC Agreement, the KPP Partnership Agreement and the KPOP Partnership Agreement (as such terms are defined in Section 1 hereof).  The “ Organizational Documents ” shall mean the LLC Agreement (as defined in Section 1 hereof) and the MLP Organizational Documents collectively.  The “ Operative Agreements ” shall mean the Transaction Documents and the Organizational Documents collectively.

The Company and the Selling Unitholders wish to confirm as follows their agreement with you in connection with the purchase of the Offered Units from the Selling Unitholders by the Underwriters.

1.                                        Representations, Warranties and Agreements of the Company.   The Company represents, warrants and agrees that:

3

(a)                                   Registration; Definitions; No Stop Order .  A registration statement (Registration No. 333-138810) on Form S-1 relating to the Offered Units has (i) been prepared by the Company in conformity with the requirements of the Securities Act of 1933, as amended (the “ Securities Act ”), and the rules and regulations (the ” Rules and Regulations ”) of the Securities and Exchange Commission (the ” Commission ”) thereunder; (ii) been filed with the Commission under the Securities Act; and (iii) become effective under the Securities Act.  Copies of such registration statement and any amendment thereto have been delivered by the Company to you as the representatives of the Underwriters (the “ Representatives ”).  As used in this Agreement:

(i)                                      “ Applicable Time ” means 8:00 a.m. (New York City time) on December 19, 2006;

(ii)                                   “ Effective Date ” means each date and time as of which such registration statement, any post-effective amendment or amendments thereto and any registration statement or amendments thereto filed pursuant to Rule 462(b) relating to the offering of the Offered Units was or is declared effective by the Commission;

(iii)                                “ Issuer Free Writing Prospectus ” means each “free writing prospectus” (as defined in Rule 405 of the Rules and Regulations) prepared by or on behalf of the Company or used or referred to by the Company in connection with the offering of the Offered Units;

(iv)                               “ Preliminary Prospectus ” means any preliminary prospectus relating to the Offered Units included in such registration statement or filed with the Commission pursuant to Rule 424(b) of the Rules and Regulations;

(v)                                  “ Pricing Disclosure Package ” means, as of the Applicable Time, the most recent Preliminary Prospectus, together with each Issuer Free Writing Prospectus set forth on Schedule VI hereto and the information set forth on Schedule VII hereto;

(vi)                               “ Prospectus ” means the final prospectus relating to the Offered Units, as filed with the Commission pursuant to Rule 424(b) of the Rules and Regulations; and

(vii)                            “ Registration Statement ” means such registration statement, as amended as of the Effective Date, including any Preliminary Prospectus or the Prospectus and all exhibits to such registration statement.

Any reference to the “ most recent Preliminary Prospectus ” shall be deemed to refer to the latest Preliminary Prospectus included in the Registration Statement or filed pursuant to Rule 424(b) on or prior to the date hereof.  The Commission has not issued any order preventing or suspending the use of any Preliminary Prospectus or the Prospectus or suspending the effectiveness of the Registration Statement, and no proceeding or examination for such purpose has been instituted or threatened by the Commission.

4

(b)                                  Company Not an “Ineligible Issuer .”  The Company was not at the time of initial filing of the Registration Statement and at the earliest time thereafter that the Company or another offering participant made a bona fide offer (within the meaning of Rule 164(h)(2) of the Rules and Regulations) of the Offered Units, is not on the date hereof and will not be on the applicable Delivery Date an “ineligible issuer” (as defined in Rule 405).

(c)                                   Registration Statement and Prospectus Conform to the Requirements of the Securities Act .  The Registration Statement conformed when filed and will conform in all material respects on the Effective Date and on the applicable Delivery Date, and any amendment to the Registration Statement filed after the date hereof will conform in all material respects when filed, to the requirements of the Securities Act and the Rules and Regulations.  The Preliminary Prospectus conformed when filed, and the Prospectus will conform, in all material respects when filed with the Commission pursuant to Rule 424(b) and on the applicable Delivery Date, to the requirements of the Securities Act and the Rules and Regulations.

(d)                                  No Material Misstatements or Omissions in Registration Statement .  The Registration Statement did not, as of the Effective Date, contain an untrue statement of a material fact or omit to state a material fact required to be stated therein or necessary to make the statements therein not misleading; provided that no representation or warranty is made as to information contained in or omitted from the Registration Statement in reliance upon and in conformity with written information furnished to the Company through the Representatives by or on behalf of any Underwriter specifically for inclusion therein, which information is specified in Section 9(f).

(e)                                   No Material Misstatements or Omissions in Prospectus .  The Prospectus will not, as of its date and on the applicable Delivery Date, contain an untrue statement of a material fact or omit to state a material fact necessary to make the statements therein, in the light of the circumstances under which they were made, not misleading; provided that no representation or warranty is made as to information contained in or omitted from the Prospectus in reliance upon and in conformity with written information furnished to the Company through the Representatives by or on behalf of any Underwriter specifically for inclusion therein, which information is specified in Section 9(f).

(f)                                     No Material Misstatements or Omissions in Pricing Disclosure Package .  The Pricing Disclosure Package did not, as of the Applicable Time, contain an untrue statement of a material fact or omit to state a material fact necessary to make the statements therein, in the light of the circumstances under which they were made, not misleading; provided that no representation or warranty is made as to information contained in or omitted from the Pricing Disclosure Package in reliance upon and in conformity with written information furnished to the Company through the Representatives by or on behalf of any Underwriter specifically for inclusion therein, which information is specified in Section 9(f).

(g)                                  No Material Misstatements or Omissions in Issuer Free Writing Prospectuses .  Each Issuer Free Writing Prospectus (including, without limitation, any

5

road show that is a free writing prospectus under Rule 433), when considered together with the Pricing Disclosure Package as of the Applicable Time, (i) did not contain an untrue statement of a material fact or omit to state a material fact necessary to make the statements therein, in the light of the circumstances under which they were made, not misleading and (ii) did not conflict with the information then contained in the Registration Statement.

(h)                                  Issuer Free Writing Prospectuses Conform to the Requirements of the Securities Act .  Each Issuer Free Writing Prospectus conformed or will conform in all material respects to the requirements of the Securities Act and the Rules and Regulations on the date of first use, and the Company has complied with all prospectus delivery requirements and any filing and record keeping requirements applicable to such Issuer Free Writing Prospectus pursuant to the Rules and Regulations.  The Company has not made any offer relating to the Offered Units that would constitute an Issuer Free Writing Prospectus without the prior written consent of the Representatives.  The Company has retained in accordance with the Rules and Regulations all Issuer Free Writing Prospectuses that were not required to be filed pursuant to the Rules and Regulations.  The Company has taken all actions necessary so that any “road show” (as defined in Rule 433 of the Rules and Regulations) in connection with the offering of the Offered Units will not be required to be filed pursuant to the Rules and Regulations.

(i)                                      Formation and Qualification .  The Company and each of the Valero MLP Parties has been duly organized and is validly existing and in good standing as a limited partnership, limited liability company or corporation, as applicable, under the laws of its jurisdiction of organization and is duly qualified to do business and in good standing as a foreign limited partnership, foreign limited liability company or foreign corporation, as applicable, in each jurisdiction in which its ownership or lease of property or the conduct of its business requires such qualification, except where the failure to be so qualified or in good standing would not, and except where the failure of the Kaneb OLP Entities to be so duly organized would not, (i) in the aggregate, reasonably be expected to have a material adverse effect on the condition (financial or otherwise), results of operations, unitholders’ or stockholders’ equity, properties, business or prospects of the Company and its subsidiaries (as defined in Rule 405) taken as a whole (a “ Material Adverse Effect ”); or (ii) subject the members of the Company to any material liability or disability; and the Company and each of the Valero MLP Parties has all power and authority necessary to own or hold its properties and to conduct the businesses in which it is engaged in all material respects as described in the Pricing Disclosure Package.

(j)                                      Ownership of the Company .  The Valero Energy Subsidiaries own 59.4% of the issued and outstanding Units in and are members of the Company, as shown on Schedule III; such Units have been duly authorized and validly issued in accordance with the limited liability company agreement of the Company (the “ LLC Agreement ”), and are fully paid (to the extent required by the LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 18-607 of the Delaware Limited Liability Company Act (the “ Delaware LLC Act ”)); and the Valero Energy Subsidiaries own such Units free and clear of all liens, encumbrances, security interests, charges or claims.

6

(k)                                   Ownership of Valero GP by the Company .  At each Delivery Date, the Company will be the sole member of Valero GP and will own 100% of the issued and outstanding membership interests in Valero GP; such membership interests have been duly authorized and validly issued in accordance with the limited liability company agreement of Valero GP (the “ Valero GP LLC Agreement ”), and are fully paid (to the extent required under the Valero GP LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 18-607 of the Delaware LLC Act); and the Company owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims.

(l)                                      Ownership of Riverwalk Holdings by the Company .  At each Delivery Date, the Company will be the sole member of Riverwalk Holdings and will own 100% of the issued and outstanding membership interests in Riverwalk Holdings; such membership interests have been duly authorized and validly issued in accordance with the limited liability company agreement of Riverwalk Holdings (the “ Riverwalk Holdings LLC Agreement ”), and are fully paid (to the extent required under the Riverwalk Holdings LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 18-607 of the Delaware LLC Act); and the Company owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims.

(m)                                Ownership of the General Partner Interest in the General Partner .  At each Delivery Date, Valero GP will be the sole general partner of the General Partner with a 0.1% general partner interest in the General Partner; such general partner interest has been duly authorized and validly issued in accordance with the limited partnership agreement of the General Partner (the “ GP Partnership Agreement ”); and Valero GP owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(n)                                  Ownership of the Limited Partner Interests in the General Partner .  At each Delivery Date, Riverwalk Holdings will be the sole limited partner of the General Partner with a 99.9% limited partner interest in the General Partner; such limited partner interest has been duly authorized and validly issued in accordance with the GP Partnership Agreement and is fully paid (to the extent required under the GP Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Revised Uniform Limited Partnership Act (the “ Delaware LP Act ”)); and Riverwalk Holdings owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(o)                                  Ownership of the General Partner Interest and Incentive Distribution Rights in the Partnership .  At each Delivery Date, the General Partner will be the sole general partner of the Partnership with a 2% general partner interest and 100% of the Incentive Distribution Rights in the Partnership; such general partner interest and Incentive Distribution Rights have been duly authorized and validly issued in accordance with the limited partnership agreement of the Partnership (the “ Partnership Agreement ”) and, in the case of the Incentive Distribution Rights, are fully paid (to the

7

extent required under the Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Act); and the General Partner owns such general partner interest and Incentive Distribution Rights, in each case, free and clear of all liens, encumbrances, security interests, charges or claims.

(p)                                  Ownership of the Partnership’s Common Units by the Company .  At each Delivery Date, Riverwalk Holdings and, at the Initial Delivery Date, Valero GP, direct wholly owned subsidiaries of the Company, will own 10,213,894 and 6,976 of the Partnership’s common units, respectively, representing a 21.38% and 0.02% limited partner interest, respectively, in the Partnership; such limited partner interests have been duly authorized and validly issued in accordance with the Partnership Agreement and are fully paid (to the extent required under the Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Act); and Riverwalk Holdings and Valero GP own such limited partner interests free and clear of all liens, encumbrances, security interests, charges or claims.

(q)                                  Ownership of Valero OLP GP by the Partnership .  At each Delivery Date, the Partnership will own 100% of the issued and outstanding capital stock of Valero OLP GP; such shares of capital stock have been duly authorized and validly issued in accordance with the certificate of incorporation and bylaws of Valero OLP GP, as amended to date, and are fully paid and nonassessable; and the Partnership owns such shares of capital stock free and clear of all liens, encumbrances, security interests, charges or claims.

(r)                                     Ownership of the General Partner Interest in Valero OLP .  At each Delivery Date, Valero OLP GP will be the sole general partner of Valero OLP with a 0.01% general partner interest in Valero OLP; such general partner interest has been duly authorized and validly issued in accordance with the limited partnership agreement of Valero OLP (the “ Valero OLP Partnership Agreement ”); and Valero OLP GP owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(s)                                   Ownership of the Limited Partner Interest in Valero OLP .  At each Delivery Date, the Partnership will be the sole limited partner of Valero OLP with a 99.99% limited partner interest in Valero OLP; such limited partner interest has been duly authorized and validly issued in accordance with the Valero OLP Partnership Agreement and is fully paid (to the extent required under the Valero OLP Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Act); and the Partnership owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(t)                                     Ownership of Kaneb Services by the Partnership .  At each Delivery Date, the Partnership will be the sole member of Kaneb Services and will own 100% of the issued and outstanding membership interests in Kaneb Services; such membership

8

interests have been duly authorized and validly issued in accordance with the limited liability company agreement of Kaneb Services (the “ Kaneb Services LLC Agreement ”), and are fully paid (to the extent required under the Kaneb Services LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 18-607 of the Delaware LLC Act); and the Partnership owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims.

(u)                                  Ownership of Kaneb GP .  At each Delivery Date, Kaneb Services, a wholly owned subsidiary of the Partnership, will be the sole member of Kaneb GP and will own 100% of the issued and outstanding membership interests in Kaneb GP; such membership interests have been duly authorized and validly issued in accordance with the limited liability company agreement of Kaneb GP (the “ Kaneb GP LLC Agreement ”), and are fully paid (to the extent required under the Kaneb GP LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 18-607 of the Delaware LLC Act); and Kaneb Services owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims.

(v)                                  Ownership of the General Partner Interest in KPP .  At each Delivery Date, Kaneb GP will be the sole general partner of KPP with a 1% general partner interest in KPP; such general partner interest has been duly authorized and validly issued in accordance with the limited partnership agreement of KPP (the “ KPP Partnership Agreement ”); and Kaneb GP owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(w)                                Ownership of the Limited Partner Interest in KPP .   At each Delivery Date, the Partnership will be the sole limited partner of KPP with a 99% limited partner interest in KPP; such limited partner interest has been duly authorized and validly issued in accordance with the KPP Partnership Agreement and is fully paid (to the extent required under the KPP Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Act); and the Partnership owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(x)                                    Ownership of the General Partner Interest in KPOP .  At each Delivery Date, Kaneb GP will be the sole general partner of KPOP with a 1% general partner interest in KPOP; such general partner interest has been duly authorized and validly issued in accordance with the limited partnership agreement of KPOP (the “ KPOP Partnership Agreement ”); and Kaneb GP owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(y)                                  Ownership of the Limited Partner Interest in KPOP .  At each Delivery Date, KPP will be the sole limited partner of KPOP with a 99% limited partner interest in KPOP; such limited partner interest has been duly authorized and validly issued in accordance with the KPOP Partnership Agreement and is fully paid (to the extent required under the KPOP Partnership Agreement) and nonassessable (except as such

9

nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Act); and KPP owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(z)                                    Ownership of the Operating Subsidiaries .  Except as set forth on Schedule IV hereto, at each Delivery Date, each of Valero OLP and KPOP, as applicable, will own 100% of the outstanding capital stock, membership interests or partnership interests, as the case may be, in each of the Operating Subsidiaries; such stock, membership interests or partnership interests have been duly authorized and validly issued in accordance with the applicable certificate of incorporation and bylaws, certificate of formation and limited liability company agreement or certificate of limited partnership and partnership agreement of each Operating Subsidiary, as the case may be (collectively, the “ Operating Subsidiaries Operative Documents ” and, as to each individual Operating Subsidiary, the “ Operating Subsidiary Operative Document ”), except where the failure of such stock, membership interests or partnership interests to be so duly authorized and validly issued would not, individually or in the aggregate, have a Material Adverse Effect, and, except in the case of the general partner interests, are fully paid (to the extent required under the applicable Operating Subsidiary Operative Document) and nonassessable (except as such nonassessability may be affected by Section 18-607 of the Delaware LLC Act or Section 17-607 of the Delaware LP Act, as the case may be); and each of Valero OLP and KPOP, as applicable, own all such stock, membership interests or partnership interests, as the case may be, free and clear of all liens, encumbrances, security interests, charges or claims (collectively, “ Liens ”).

(aa)                             No Other Subsidiaries .  The Company does not own or control, directly or indirectly, any corporation, association or other entity other than the subsidiaries listed in Exhibit 21 to the Registration Statement.  None of the subsidiaries of the Company (other than the General Partner and the Partnership) is a “significant subsidiary” (as defined in Rule 405).  None of the subsidiaries of the Partnership (other than Valero OLP, KPOP, Support Terminals Operating Partnership, L.P., a Delaware limited partnership (“ STOP ”) and Shore Terminals LLC, a Delaware limited liability company (“ Shore Terminals ”)) is a “significant subsidiary” (as defined in Rule 405).

(bb)                           Capitalization .  At the Initial Delivery Date, the issued and outstanding Units of the Company will consist of 42,500,000 Units.  Other than the restricted Units granted to the directors of the Company under the Valero GP Holdings, LLC Long-Term Incentive Plan, the Units will be the only limited liability company membership interests of the Company outstanding at each Delivery Date.

(cc)                             No Preemptive Rights, Registration Rights or Options .  Except as identified in the most recent Preliminary Prospectus and the Prospectus, there are no (i) preemptive rights or other rights to subscribe for or to purchase, nor any restriction upon the voting or transfer of, any equity securities of the Company, Valero GP, Riverwalk Holdings or the General Partner; or (ii) outstanding options or warrants to purchase any securities of the Company, Valero GP, Riverwalk Holdings or the General Partner.  Neither the filing of the Registration Statement nor the offering or sale of the Offered Units as contemplated by this Agreement gives rise to any rights for or relating

10

to the registration of any Units or other securities of the Company, Valero GP, Riverwalk Holdings or the General Partner.

(dd)                           Authority and Authorization .  At each Delivery Date, all corporate, partnership and limited liability company action, as the case may be, required to be taken by any of the Company or the Valero MLP Parties or any of their respective unitholders, stockholders, members or partners for the authorization, sale and delivery of the Offered Units, the execution and delivery of the Operative Agreements and the consummation of the transactions contemplated by this Agreement and the Operative Agreements, shall have been validly taken.

(ee)                             Authorization, Execution and Delivery of this Agreement .  This Agreement has been duly authorized and validly executed and delivered by the Company.

(ff)                                 Authorization, Execution, Delivery and Enforceability of Certain Agreements .  At or before the Initial Delivery Date, the Operative Agreements will have been duly authorized, executed and delivered by the parties thereto and each will be a valid and legally binding agreement of the parties thereto, enforceable against such parties in accordance with its terms; provided that , with respect to each agreement described in this Section 1(ff), the enforceability thereof may be limited by bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws relating to or affecting creditors’ rights generally and by general principles of equity (regardless of whether such enforceability is considered in a proceeding in equity or at law); provided further ; that the indemnity, contribution and exoneration provisions contained in any of such agreements may be limited by applicable laws and public policy.

(gg)                           No Conflicts .  None of the offering or sale by the Selling Unitholders of the Offered Units, the execution, delivery and performance of this Agreement by the Company and the Selling Unitholders and the Operative Agreements by the Company, the Selling Unitholders and the Valero MLP Parties that are parties thereto or the consummation of any other transactions contemplated by this Agreement or the Operative Agreements (i) conflicts with or will conflict with, or constitutes or will constitute a violation of, the certificate of limited partnership or agreement of limited partnership, certificate of formation or limited liability company agreement, the charter or bylaws, or any other organizational documents of the Company or any of the Valero MLP Parties, (ii) conflicts with or will conflict with, or constitutes or will constitute a breach or violation of, or a default (or an event that, with notice or lapse of time or both, would constitute such a default) under, any indenture, contract, lease, mortgage, deed of trust, note agreement, loan agreement or other agreement, obligation, condition, covenant or instrument to which the Company or any of the Valero MLP Parties is a party or by which any of them are bound or to which any of their respective properties is subject, (iii) violates or will violate any statute, law, rule or regulation, or any judgment, order or decrees of any court, regulatory body, administrative agency, governmental body, arbitrator or other authority having jurisdiction over the Company or any of the Valero MLP Parties or any of their properties or assets, or (iv) will result in the creation or imposition of any Lien upon any property or assets of any of the Valero MLP Parties, except, in the case of clauses (ii), (iii) and (iv), for such conflicts, breaches, violations,

11

defaults, Liens, charges or encumbrances as would not, individually or in the aggregate, have a Material Adverse Effect, or could materially impair the ability of the Company or any of the Valero MLP Parties to perform their obligations under this Agreement or the Transaction Documents.

(hh)                           No Consents .  No permit, consent, approval, authorization, order, registration, filing or qualification of or with any court, governmental agency or body is required in connection with the execution and delivery of this Agreement by the Company or the consummation of the Operative Agreements by the Company, the Selling Unitholders and Valero MLP Parties that are parties thereto, except for (i) such permits, consents, approvals and similar authorizations required under the Securities Act, the Securities Exchange Act of 1934, as amended (the “ Exchange Act ”) and state securities or “Blue Sky” laws, (ii) such consents that have been, or prior to the Delivery Date will be, obtained, (iii) such consents that, if not obtained, would not have a Material Adverse Effect and (iv) as disclosed in the most recent Preliminary Prospectus and the Prospectus.

(ii)                                   No Defaults .  Neither the Company nor any of the Valero MLP Parties is in (i) violation of its agreement of limited partnership, limited liability company agreement, certificate of incorporation or bylaws or other organizational documents, or of any law, statute, ordinance, administrative or governmental rule or regulation applicable to it or of any decree of any court or governmental agency or body having jurisdiction over it or (ii) breach or default (or an event which, with notice or lapse of time or both, would constitute such an event) in the performance of any term, covenant or condition contained in any bond, debenture, note or any other evidence of indebtedness or in any agreement, indenture, lease or other instrument to which it is a party or by which it or any of its properties is subject which breach, default or violation would, if continued, have a Material Adverse Effect or could materially impair the ability of the Company or any of the Valero MLP Parties to perform their obligations under this Agreement or the Transaction Documents.

(jj)                                   Conformity of Units to Description in the most recent Preliminary Prospectus and Prospectus .  The Units conform in all material respects to the description thereof contained in the most recent Preliminary Prospectus and Prospectus.

(kk)                             No Integration .  None of the Company or any Selling Unitholder has sold or issued any securities that would be integrated with the offering of the Offered Units contemplated by this Agreement pursuant to the Securities Act, the Rules and Regulations or the interpretations thereof by the Commission.

(ll)                                   No Material Adverse Change .  Neither the Company nor any of the Valero MLP Parties has sustained, since the date of the latest audited financial statements included in the most recent Preliminary Prospectus and the Prospectus, any loss or interference with its business from fire, explosion, flood or other calamity, whether or not covered by insurance, or from any labor dispute or court or governmental action, order or decree, and since such date, there has not been any change in the capitalization or long-term debt of the Company or any of the Valero MLP Parties or any adverse change, or

12

any development involving a prospective adverse change, in or affecting the condition (financial or otherwise), results of operations, unitholders’ or stockholders’ equity, properties, management, business or prospects of the Company or any of the Valero MLP Parties taken as a whole, in each case except as would not, in the aggregate, reasonably be expected to have a Material Adverse Effect.  Since the date of the latest audited financial statements included in the most recent Preliminary Prospectus and the Prospectus, neither the Company nor any of the Valero MLP Parties has incurred any liability or obligation, direct, indirect or contingent, or entered into any transactions, not in the ordinary course of business, that, individually or in the aggregate, is material to the Company or any of the Valero MLP Parties, taken as a whole, otherwise than as set forth or contemplated in the most recent Preliminary Prospectus and the Prospectus.

(mm)                       Conduct of Business .  Since the date as of which information is given in the most recent Preliminary Prospectus and the Prospectus, neither the Company nor any of the Valero MLP Parties have (i) incurred any liability or obligation, direct or contingent, other than liabilities and obligations that were incurred in the ordinary course of business, (ii) entered into any material transaction not in the ordinary course of business or (iii) declared, paid or made any dividend or distribution on any class of security, except in the case of the Valero MLP Parties, in the ordinary course consistent with past practice.

(nn)                           Financial Statements .  The historical financial statements (including the related notes and supporting schedules) included in the most recent Preliminary Prospectus and the Prospectus (and any amendment or supplement thereto) comply as to form in all material respects with the requirements of Regulation S-X under the Securities Act and present fairly the financial condition, results of operations and cash flows of the entities purported to be shown thereby at the dates and for the periods indicated and have been prepared in conformity with accounting principles generally accepted in the United States applied on a consistent basis throughout the periods involved.  The summary historical and pro forma financial data included in the most recent Preliminary Prospectus and the Prospectus (and any amendment or supplement thereto) under the captions “Prospectus Summary—Summary Historical and Pro Forma Financial Data—Valero GP Holdings, LLC” and “Prospectus Summary—Summary Historical and Pro Forma Financial Data—Valero L.P.” and the selected historical and pro forma financial data set forth under the captions “Selected Historical and Pro Forma Financial Data—Valero GP Holdings, LLC” and “Selected Historical and Pro Forma Financial Data—Valero L.P.” are accurately presented in all material respects and prepared on a basis consistent with the audited and unaudited historical financial statements and pro forma financial statements, as applicable, from which such data has been derived.

(oo)                           Pro Forma Financial Statements .  The pro forma financial statements included in the most recent Preliminary Prospectus and the Prospectus (and any amendment or supplement thereto) comply as to form in all material respects with the applicable requirements of Regulation S-X and have been prepared in accordance with the Commission’s rules and guidelines with respect to pro forma financial statements and have been properly computed on the bases described therein.  The assumptions used in the preparation of such pro forma financial statements are, in the opinion of the

13