Are you trying to yum remove dhcp or libdhcp?  The yum output you pasted here
doesn't make sense to me.

libdhcp, oddly enough, I don't even have dhcp on this system.

libdhcp is required by some core system components.  When I try to remove it on
rawhide, I get this from yum:

$ sudo yum remove libdhcp
Loading "fedorakmod" plugin
Loading "changelog" plugin
Loading "skip-broken" plugin
Loading "downloadonly" plugin
Loading "merge-conf" plugin
Loading "protect-packages" plugin
Loading "allowdowngrade" plugin
Setting up Remove Process
Resolving Dependencies
--> Running transaction check
---> Package libdhcp.i386 0:1.27-2.fc8 set to be erased
--> Processing Dependency: libdhcp.so.1 for package: libdhcp-devel
--> Processing Dependency: libdhcp.so.1 for package: mkinitrd
--> Processing Dependency: libdhcp.so.1 for package: nash
--> Processing Dependency: libdhcp.so.1 for package: anaconda
--> Processing Dependency: libdhcp = 1.27-2.fc8 for package: libdhcp-devel
--> Processing Dependency: libdhcp for package: nash
--> Running transaction check
---> Package libdhcp-devel.i386 0:1.27-2.fc8 set to be erased
--> Processing Dependency: libdhcp-devel = 1.27-2.fc8 for package: libdhcp-static
---> Package mkinitrd.i386 0:6.0.16-1.fc8 set to be erased
--> Processing Dependency: mkinitrd for package: mkinitrd-devel
---> Package nash.i386 0:6.0.16-1.fc8 set to be erased
--> Processing Dependency: libbdevid for package: python-pyblock
--> Processing Dependency: libbdevid.so.6.0.16 for package: libbdevid-python
--> Processing Dependency: nash = 6.0.16-1.fc8 for package: libbdevid-python
---> Package anaconda.i386 0:11.3.0.31-1 set to be erased
--> Processing Dependency: anaconda = 11.3.0.31-1 for package: anaconda-runtime
--> Running transaction check
---> Package anaconda-runtime.i386 0:11.3.0.31-1 set to be erased
--> Processing Dependency: anaconda-runtime for package: pungi
---> Package libbdevid-python.i386 0:6.0.16-1.fc8 set to be erased
---> Package libdhcp-static.i386 0:1.27-2.fc8 set to be erased
---> Package mkinitrd-devel.i386 0:6.0.16-1.fc8 set to be erased
---> Package python-pyblock.i386 0:0.30-1 set to be erased
--> Running transaction check
---> Package pungi.noarch 0:1.1.1-1.fc8 set to be erased
--> Finished Dependency Resolution

Dependencies Resolved

=============================================================================
 Package                 Arch       Version          Repository        Size 
=============================================================================
Removing:
 libdhcp                 i386       1.27-2.fc8       installed         132 k
Removing for dependencies:
 anaconda                i386       11.3.0.31-1      installed          14 M
 anaconda-runtime        i386       11.3.0.31-1      installed         3.2 M
 libbdevid-python        i386       6.0.16-1.fc8     installed         7.1 k
 libdhcp-devel           i386       1.27-2.fc8       installed          75 k
 libdhcp-static          i386       1.27-2.fc8       installed         110 k
 mkinitrd                i386       6.0.16-1.fc8     installed          97 k
 mkinitrd-devel          i386       6.0.16-1.fc8     installed          12 k
 nash                    i386       6.0.16-1.fc8     installed         232 k
 pungi                   noarch     1.1.1-1.fc8      installed         126 k
 python-pyblock          i386       0.30-1           installed         172 k

Transaction Summary
=============================================================================
Install      0 Package(s)         
Update       0 Package(s)         
Remove      11 Package(s)         

Is this ok [y/N]: 


Which _is_ expected.

Another way of seeing what requires libdhcp.so.1:

$ rpm -q --whatrequires libdhcp.so.1
libdhcp-devel-1.27-2.fc8
nash-6.0.16-1.fc8
mkinitrd-6.0.16-1.fc8
anaconda-11.3.0.31-1

/sbin/nash is linked with it, and nash is part of mkinitrd.  In anaconda, our
_isys.so Python module requires it.

I can understand the requirement for anaconda, but why nash? On an FC6 machine,
I have:
[root@spaz ~]# rpm -qa | grep dhcp
[root@spaz ~]# rpm -qa | grep anaconda
[root@spaz ~]# rpm -qa | grep kernel
kernel-2.6.22.2-42.fc6
kernel-2.6.20-1.2962.fc6
kernel-headers-2.6.22.2-42.fc6
[root@spaz ~]# rpm -qa | grep mkinit
mkinitrd-5.1.19.0.3-1
mkinitrd-5.1.19.0.3-1
[root@spaz ~]# rpm -qa | grep nash
nash-5.1.19.0.3-1
[root@spaz ~]# 

nash needs it because it can bring up network interfaces.  The network command
in nash does that (which is unfortunately missing from the nash.8 man page, a
bug should be filed against mkinitrd for that).

Closing this one as NOTABUG.

Yeah, I was just looking at that in /nash/network.c

Sorry, I just get frustrated with having to recode extraneous packages out from
systems I'm trying to make as lightweight as possible. Maybe I should just
switch to a different distro for these anyway.

Given the goals of Fedora, it can only be made to be so light.

An easy way to see what constitutes a barebones system, you should do a
Kickstart install.  Add a %packages section to the kickstart file that looks
like this:

%packages
-*

Yes, a hyphen and asterisk.  That tells the depsolver that you want _nothing_ on
the target system except what is in the base system.  So all packages will be
removed and the depsolver will bring in just what's needed for the base system.
 It's interesting [to me] to see how rapidly things change in the Fedora world.

The libdhcp package you're wanting to remove is only about 125k on the system. 
If you really want to make a stripped down lightweight system, you should
consider removing /usr/share/doc as well as /usr/share/locale (and even other
things from /usr/share, like man pages).  The /usr/share/doc directory on my
laptop takes up 225M on my system.  Docs aren't packaged separately, so you'd
have to remove /usr/share/doc on the target system after you set them up (maybe
%post in a kickstart install script).

Don't get me wrong, I think Fedora's the best OS out there (well, FC6 IMO, but I
still use F7 on my main system), just that it might not be suitable for what I'm
trying to piece together (not embedded, but targeted corporate desktops).
libdhcp is the least of my issues right now, I just thought it'd be nice to be
able to have it completely gone (some systems will use this anyway) and thought
it odd that it was going to remove the kernel. That and I have too much free
time today and thought I'd complain about something before actually looking at
what was going on. Sorry for that.

I do want to get as lightweight as possible, but rather than some kickstart
hacks, I'm more likely to segregate the packages and submit them and, if they're
not accepted, spin off my own distro from them. This is because these will
eventually become commercial products and can't have things like package updates
completely borking everything I've done, so any changes have to be propagated up
to the package repos these systems are going to use.

Right now, about 80% of the desktop systems I sell run Fedora, and (politics
aside) with Fedora's excellent track record at fixing issues, extremely stable
operation and excellent hardware support, I'd like to keep it that way, if not
move those percentages up. Having fewer different distros means less support
training and a more uniform user base.

But I'm rambling off topic. See, too much free time.

Thanks

Understandable.  Well, good luck.  You said the magic word ("corporate") and
what I tell people who are looking for something a little less gigantic (not
10000 packages, for instance), have a look at CentOS.  You probably know it. 
It's RHEL rebuilt by the community and with RH trademarked stuff removed.  The
big selling point it has is that it doesn't diverge from RHEL at all (except to
remove the trademarked things like artwork and RHN components), so people can
have a system capable of running RHEL-certified applications or a system that
works like RHEL (Howtos for RHEL and books for RHEL will apply to CentOS with
minimal differences).

I'm all for fewer distributions too.

Good luck.