A technique enables Traffic Engineering (TE) on paths between customer edge devices (CEs) across a provider network (“CE-CE paths”) in a computer network. According to the novel technique, TE is configured on a link from a sending provider edge device (PE) to a first CE (“PE-CE link”), e.g., a CE of one or more virtual private networks (VPNs). The sending PE conveys TE information of the PE-CE link to one or more receiving PEs in the provider network. Upon receiving the TE information, each receiving PE expands a TE database (TED) for information regarding the provider network (i.e., a “core TED”) to include TE-configured PE-CE links, e.g., by updating one or more corresponding VPN TEDs (VTEDs) for each VPN maintained by the receiving PE. Once the receiving PEs have the TE information for configured PE-CE links from the provider network, one or more TE techniques may be applied to paths from a second CE of the receiving PE to the first CE (a CE-CE path) to thereby facilitate, e.g., establishment of TE-LSPs along CE-CE paths.