Exhibit 5.6

[Letterhead of Fennemore Craig, P.C.]

February 26, 2013

Dycom Investments, Inc.

11770 U.S. Highway 1, Suite 101

Palm Beach Gardens, Florida 33408

RE: That certain registration statement on Form S-4, as amended from time to time (the “Registration Statement”), made by Dycom Investments, Inc., a Delaware corporation (the “Company”), as filed with the United States Securities and Exchange Commission (“SEC”) under the Securities Act of 1933, as amended (the “Securities Act”), relating to the issuance of $90,000,000.00 principal amount of 7.125% Senior Subordinated Notes due 2021 (the “Exchange Notes”)

Ladies and Gentlemen:

We have been asked to render a legal opinion, as special counsel in the State of Arizona (the “State”) to Pauley Construction Inc., an Arizona corporation (“Subsidiary”), being a subsidiary of Dycom Industries, Inc., a Florida corporation (“Dycom”), which is the parent corporation of the Company, in connection with the Registration Statement and the prospectus forming a part of the Registration Statement. Unless otherwise defined herein or unless the context requires otherwise, capitalized terms defined in the Registration Statement shall have the same meaning when used herein.

In connection with rendering our opinion, we have examined the following documents:

a. The Registration Statement;

b. The Indenture dated January 21, 2011 (the “Indenture”) among the Company, the guarantors party thereto and U.S. National Bank Association, as Trustee;

c. The Second Supplemental Indenture dated December 12, 2012 (the “Second Supplemental Indenture”) among Subsidiary, the Company, the other guarantors party thereto and U.S. National Bank Association, as Trustee;

d. The Third Supplemental Indenture dated February 26, 2013 (the “Third Supplemental Indenture”) among Subsidiary, the Company, the other guarantors party thereto and U.S. National Bank Association, as Trustee; and

e. The form of Notation of Guarantee (the “Notation of Guarantee”).

1

The Indenture, Second Supplemental Indenture, Third Supplemental Indenture and Notation of Guarantee are herein collectively referred to as the “Documents.” We have been retained by Subsidiary to review the Documents only for the purpose of reviewing such documents in connection with the rendering of the opinions contained herein.

As to certain matters of fact bearing upon the opinions expressed herein, we have reviewed and relied on:

(i) Articles of Incorporation of Subsidiary dated April 18, 1991, as filed with the State of Arizona, Office of the Corporation Commission on April 19, 1991 (the “Articles”);

(ii) Bylaws of Subsidiary dated April 18, 1991 (the “Bylaws”);

(iii) Certificate of Good Standing for Subsidiary issued on November 27, 2012, by the State of Arizona, Office of the Corporation Commission (“Good Standing Certificate”); and

(iv) Secretary’s Certificate dated December 12, 2012, Supplemental Secretary’s Certificate dated December 28, 2012, and Supplemental Secretary’s Certificate II dated February 26, 2013 (collectively, “Secretary’s Certificate”), and all exhibits attached thereto, including resolutions authorizing, among other things, the exchange offer described in the Registration Statement.

The Articles, Bylaws, Good Standing Certificate and Secretary’s Certificate are herein collectively referred to as the “Authority Documents.”

In rendering the opinions expressed herein, we have assumed the following:

(a) The representations and warranties and other statements contained in the Documents and the Authority Documents are true, correct and complete as to all matters of fact;

(b) The Registration Statement contains all disclosures of fact in a true and accurate manner as required by any Federal or state law.

(c) The Documents have been duly authorized and accepted by the parties thereto, other than Subsidiary; the Documents constitute a legally valid and binding obligations of the parties thereto, other than Subsidiary, enforceable against the parties thereto, other than Subsidiary, in accordance with their terms; and the status of the Second Supplemental Indenture, Third Supplemental Indenture and Notation of Guarantee as legally valid and binding obligations of the parties thereto, other than Subsidiary, is not affected by any (i) breaches of, or defaults under, agreements or instruments, (ii) violations of statutes, rules, regulations or court or governmental orders, or (iii) failures to obtain required consents, approvals or authorizations from, or make required registrations, declarations or filings with, governmental authorities;

(d) There are no oral or written statements or agreements that modify, amend or vary, or purport to modify, amend or vary, any of the terms of the Documents;

2

(e) Purchasers will receive no interest, charges, fees or other benefits or compensation in the nature of interest in connection with the transaction except those that the Company and/or Subsidiary has agreed in writing in the Documents to pay, which includes those that are received under the Financing Transactions (as described in the Registration Statement);

(f) All signatures by the parties to the Documents, including Subsidiary, are genuine; all documents submitted to us as originals are authentic; and all documents submitted to us as conformed, photographic or electronic copies conform to the original documents; and

(g) As it relates to Subsidiary, the consideration for the guaranty described in the Registration Statement is sufficient and adequate consideration, and reasonable equivalent value has been given.

Based upon the foregoing assumptions and subject to the qualifications hereinafter set forth, it is our opinion that, as of the date hereof:

1. Based on the Authority Documents, Subsidiary is a corporation duly formed, validly existing and in good standing under the laws of the State.

2. Subsidiary has the requisite corporate power and authority to execute and deliver each of the Second Supplemental Indenture, Third Supplemental Indenture and Notation of Guarantee, and perform its obligations thereunder.

3. The transactions contemplated by the Documents, and the execution, delivery and performance by Subsidiary of its obligations under the Second Supplemental Indenture, Third Supplemental Indenture and Notation of Guarantee, have been duly authorized by all requisite corporate action of Subsidiary. The Second Supplemental Indenture and Third Supplemental Indenture have been duly executed and delivered by Subsidiary.

We express no opinion as to the validity or enforceability of any of the Documents or to the truth or accuracy of the factual statements contained in the Registration Statement.

The Documents indicate they are to be governed by the laws of the State of New York. We have no knowledge of those laws and express no opinion thereon. We are qualified to practice law in the State and we do not purport to be experts on, or to express any opinion herein concerning, any matter governed by the laws of any jurisdiction other than the laws of the State and the Federal law of the United States, except that we express no opinion as to the application or effect of any Federal or state securities or anti-trust laws, rules or regulations on or to the transaction. With respect to such law, our opinions are as to what the law is or might reasonably be expected to be at the date hereof, and we assume no obligation to revise or supplement this opinion due to any change in the law by legislative action, judicial decision or otherwise. Furthermore, nothing in this letter is intended to, and this letter shall not be deemed to, create any obligation on the part of this firm to undertake or assume any responsibility or obligation to file or record any documents, file any continuation statements, prepare or file any amendments or modifications, or take any steps or actions whatsoever after the date of this letter.

3

We do not render any opinion with respect to any matters other than those expressly set forth above. We are furnishing this opinion to the Company and its successor and assigns, and it may be relied upon by Shearman & Sterling, LLP, as the Company’s counsel, in connection with the Documents and the filing of the Registration Statement, and we hereby consent to the filing of this letter as an exhibit to the Registration Statement. In giving this consent, we do not hereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act and the rules and regulations promulgated thereunder.

Except as otherwise provided in the immediately preceding paragraph, this opinion may not be otherwise reproduced, quoted in whole or in part, filed publicly, or circulated, or relied upon, for any other purpose nor used in connection with any other transaction without our prior written consent.

Sincerely,

FENNEMORE CRAIG, P.C.

    /s/ Laura A. Lo Bianco

for Fennemore Craig, P.C.

CLR/LLOB

4