How to recover the deleted partition and get its UUID in macOS
You have to destroy the GUID partition table and create a new one. The UUIDs of the various partition types are fixed. You can get some or most of them here: Partition type GUIDs.

Below I assume that your MacBook Air contains an SSD and the main partition was formatted as CoreStorage volume. You can check this in Recovery Mode with a method outlined here: OS volume shows as type 'FFFFFFFF-FFFF-FFFF-FFFF-FFFFFFFF' (last part)

Preparation:


Detach any external drive (especially your external Time Machine backup drive)
Restart to Internet Recovery Mode by pressing alt cmd R at startup.

The prerequisites are the latest firmware update installed, either ethernet or WLAN (WPA/WPA2) and a router with DHCP activated.
On a 50 Mbps-line it takes about 4 min (presenting a small animated globe) to boot into a recovery netboot image which usually is loaded from an Apple/Akamai server.

I recommend ethernet because it's more reliable. If you are restricted to WIFI and the boot process fails, just restart your Mac until you succeed booting.
You can either use fdisk or gpt to remove the MBR at block 0. If you use an admin user prepend sudo using the gpt .... commands.
First get an overview. This step is important before you destroy the gpt, because it's the source to rebuild it from scratch:

gpt -r show /dev/disk0

Then delete the gpt:

diskutil unmountDisk /dev/disk0
gpt destroy /dev/disk0

Create a new GUID partition table:

gpt create -f /dev/disk0

Finally add all common Mac partitions one by one based on details shown in the gpt -r show /dev/disk0 output:

gpt add -b 40 -s 409600 -i 1 -t C12A7328-F81F-11D2-BA4B-00A0C93EC93B /dev/disk0
gpt add -b 134167720 -s 1269760 -i 3 -t 426F6F74-0000-11AA-AA11-00306543ECAC /dev/disk0
gpt add -b 409640 -s 133758080 -i 2 -t 53746F72-6167-11AA-AA11-00306543ECAC /dev/disk0


Hint: You may add and remove partitions in an arbitrary order if you keep the right index number. In the above commands I added the third partition (... -i 3 ...) before adding the second partition (... -i 2 ...). You don't have to unmount disk0 then because the partitions i=1 and i=3 don't contain auto-mounted volumes while the second partition does.
Check the disk with diskutil verifyDisk disk0
Check the disk with diskutil verifyVolume disk0s2




Resizing the main volume to fill the whole disk

Finally you want to resize the main volume to fill the whole disk.


Get an overview with:

diskutil cs list


You may have several CoreStorage Logical Volume Groups, if you boot from an external drive with a full system! Use the proper one!
Resize the whole stack:

diskutil cs resizeStack lvUUID size #lvUUID is the UUID of the Logical Volume. Usually it's the last one listed.


Booted to Yosemite you can use 0g for the size to expand it. 0g is a "magical" size here.

diskutil cs resizeStack lvUUID 0g


Booted to El Capitan or later you have to use a real size like 120g. If you get an error use a slightly smaller size like 119g or199500m.

diskutil cs resizeStack lvUUID 120g