[Büten Zar]

[Link]

Comentarios Büten Zar FB

Letra

Ejercicio 1 Ejercicio 2 Ejercicio 3 Ejercicio 4

Ejercicio 5 Ejercicio 6 Ejercicio 8

Ejercicio 9 Ejercicio 10 Ejercicio 11 Ejercicio 12

Ejercicio 13 Ejercicio 14 Ejercicio 15 Ejercicio 16

Ejercicio 17 Ejercicio 18 Ejercicio 19 Ejercicio 20

Ejercicio 21 Ejercicio 22
 [Büten Zar]
Menu
[Link]

0 6 crJ.'.{or ",Jo'g*o{o5
{*rr{¡a1 ü. G lienen \ uárlices e incluyen Uñ [Link] ?

.l
l eet
rti
El unicc¡ c,cic É; 50f!
q.
.l
bq , ,l

--- /./\ t
i

I i
a- :. -. aj'
q '- --ü
rd ¿ d
,
I
:

c '-',
,l
,'r' I
L"
a
b b
i"¿ L._- .,-,
I
. i¿, 1
.-o'--..\
\\_ I
t \ \'ié
4.
r\
\r----;- !¿
/ J* -'é
.' - $-.-..- t L- v
a
I J

U: V-c

b
G, o

,l

f . tl !6, ={ri U:!-a

il
u-{".6?
!

\ 6r " e - {",6i
h I
J

O t.*.* u\ suü oro{o á.6,nlu.,üo p$, ul c.",¡."fo Jt uá'i'tul Ü: Iu.",1.{,,,,1

t
t
a

f CJ
I
I
i
E-.'--
t J
 [Büten Zar]
il sQo.§ ¿,=14,.1 e"=\o,Jl
[Link]

iltG-e,)-e" ffi (s -e,) -e,, S e-{e,,e"t

b
\_---a |.\
igroles t)
I
¡
r\
t' "l

lo --> Üw
Po'ro q'" 6t "(v' ' E')

!" Jub" .u*gh, q,* *nir" lo, ,rí.1¡..r

no irrh,.ilo

,/¡
J.l *b¡^{o [Link] .l6rnn crrls'fq [Link] es{í
h
en g pero no en 6r"

Vr=V

nu *o.o ü. ,ubgrofo, .[Link]".t¡ =*f {,,r,---,lell = z\

g,ltl = ?q
.:
t: .:,'_:. :
, '
'_ ,.',:..,
:.';.+j:: ,
",,Jt-'i,-.++,,,{.
' , .
-.1

Sor\' conexos si.-,V- h.y. €,V .,.hr*, un eqmntño

gu.. [o, uoe.
Flllt
Entonces so\o Qucüo'saerrr arrs{ar Joi c¡clo . .!.¡or,lo* lo.s si6ortcn{.i
: .- .
.
:

gpslonrs G , q''u'{o.,II''r' ,6'.

I o.,.], g -i[c .J ]

t k", [Link] <iu;t* 3 [Link].s , .o{ ooces 2.6 .,,

6rl
,

. q. seq [Link] "

3u'o. [Link] :

:-. ir;":¡.
 [Büten Zar]
EJnt",.,o-2 Menu
[Link]
E^.o,uio g^ '¿roto G lu, Jenflo\ Jn, virf¡..s u y v lul", go,

k(e -u\ = k(e) r.(g-*) > r<(c)

 [Büten Zar]
( [Link]
Menu ui't¡ ce l ' A'[o\"
rt 6r (:l *

0 q Or1
o t.
lr,
6r(¡)-- \ §¡-;-'*
r r' 6.tq1" 3
2\
\
,i

^\
' ,'"'= ' .,t
$
?
o
6
*..
l
a ts^- :
\ \t _'§

q',
L
5
5'
{, .r\
L§: &----
(
I

)¡. 3.,irl¡.es Je l

: \l 6rix) = ¡ L +

ttr. :

i', .

i
6

son isoÉ'wtot

o
no esi sor$0r6 c$n
Rq\ t- '
&i\ ttb,;
r f -\
$G)

I
(,
ffi,** {0 *r,Jots
{0 qr,s-{ar
 [Büten Zar]
Menu
[Link]
H*\lo nufrntro
?
J. sub6tqfo, coñexos recuLr{Jorer no rro*orfor J. lo f,¿r.o
"\ 2.
35

lEl >. lvl -t

lel >, I

{,o.,. quc ser ro,.rt.t Jor .:) v1 =v

tiunu 1". ser Sx.y eV tt.r.e

lue
1 un qtrmilno X,y =J n§ se p*ü =,..o,
[...] n, {[Link]
^, lr,s}
[Link] n. I [Link]
{ -6
3 6 - Iq¡l

f
I
60ñ^l
isorootbt t fh)
i
,

f(¡)

5
- 6-{".,..1 Tot"l ¿l: Cr ==¡ tO -. L cosos - \ ¡..rkor{or = !l
(
for..ol
t'- ' )
[Link]
"

:,'"(

:g
 [Büten Zar]
L.."ieto
_.+---- 5
[Link]
Menu

§ T- r ,
1
', r"^--' ¡ :r ?."- \
:l 1 I
]
t-

e
.-¿"- "F
.A*-... "f
al "h
t\.1
oo h&y ciq\tas Je
1 c,.io J* tor6o I
\ong B n0 §on r§orrr¿r{oS

t\
.^-
\.'\
t) Cr
t ñ- 1
t\
;i
_.

?I
h t\.
i -.,
-l
6
{
I

l
I
I
i I I
l I
I I
\l a i
:
6 -.. i

K-. \3
D I

I
¿i
8 aristct:
q a¡, c\srL fro §cr^ iSOmOr{or

GJ
t

1t t
§t-_ l
I '. ci
\i
6,
¿-,É
-. ..¡, - .¿-.
-1
r.e C

\23
tt
a i
I

|:
6.
,6o ü
0.
,.---'- 5
\,
.\1"

o ,"
/
a. t",
{'
t r- '-7
1 --/-
.y',¿-
.-- r'' .5
a,
l
,l
!
I
I
- .¡".

.,,
i
,,/' ,
V't r
r. '- *.--.:-.^---'*-- r
..r t 3
tl

f
'd 5on tsotmortog
 [Büten Zar]
Menu [Link]

I D.*r.r\r. T, Jo, 6*tot son iso¡*[Link] rt*) s,rs .o*pL*.n{r, lo soñ"

E',r{u,
(+) Gtr6¡ rorr i;o¡.orfos I f , u. r üe b,yu.{,uo .l"l
-¡ 1* :

[., ,1 G Er e If.) ,{(dl GEe

Ut*o1 lq rñi6rmq' [un'i'ín f I pro[cmos
1r.
I
*n .l\. 6, , q son isorrnorfor^
G*. I es [Link],,* , .l+* p*&, ,que {* ,1f . E, *=
f
irH , {G} I .E
l: .
f -,r1 € E, F+ [*.rl + E, {«a,{tr)f * u F)[(J,$(r)], EL
=,L..nJ*á¿"f
*::
"
s,:
,:_
t? ,
br¡6¡Son
.
o-,pL*'*.rto..,or.
(el Análo6o.

{ 3 - ci clc¡ :.:

{ h - e¡¿lo t a- ciclo { ?'.. c¡.t

: l'
t \-
"i"lo .:
:a
,i,{i:s:

{ y 2 soñ ¡sor-árfos
*3r:_+1.

\L,

.j

:ir::::,.;

.; '-_"

.¡.
 t [Büten Zar]
ffi Dt.,rnr oe e,l nlr*qro dt o,r,r1* l, e en [Link] ¿.1 hürnero d. [Link]

+,I \ .,\,[Link]\ - \il

-*----,-
t,
G. (v,E)
: .. .
i ..:
h,:.
. a,r:l,
\)- (v ,E)
lÉ \= \v\ (tvt -J\ 't El

ru 0"1. r,",ri oe "\ nú r,ne ,o l.. o..rslcs J. un X*to outo.o*pk *[Link].o d, ord.n
fi.

¡
G i sormorto 1,
con\3:
G lEl = tEl
a.:. ..- I ;

r\el . lvl (\y1:1,).

2

lel = [Link] -t\ a

n (.,-,)
\i

c'"rto',¡* u§ *"{" eat*¡le¡mtotig le,,'oJe¡ oJ.n 5.

§ 01ot
Iel = 3 ortJo. on{eq tl
lEl

orJ.n 5 . lvl-- 5

G
 [Büten Zar]
[Link]
O U"1r,' r,,r',ne ?,,rc' trní uo\ure, J. r\ existq un .ru{n."*pt.¡"",rnlario
[Link] áu

o. f,*.' (\ .

1e\ = ll::r)
Ll

\g\ l;*.,* quo ser n*turol :, Lq=ü f

(n-r) = ü ":'[-;; ü *11
 [Büten Zar]
b¡ercr ci o I Menu [Link]

6r\ Gr?
4 \.. \,, Lrt
6rS ,/
'"er7
\ oGr{i

,l
611 6r{

ü 11t\ : Ix€vn" t"\

E\E\ : I + { + 5 +) + Z t 6 + 1+ ,t ¡{ :20

Uqr= !d J

4 5 C uá"lrr ulr{ i"et J. 3,*áo i nn gar 'l ,nr* ?

1{o",¡
,
b ' llCe(
),.
\¡er
 [Büten Zar]
Menu
[Link]
-) j - rego\crr coñ q [Link]*s

:. 1e\ = E,nn(*\
* erJ

:lsl = B. n
§ "[*i 6-1

b) t0 o.,r{aE , ? uí r{¡.*, con q, los Je*ls eon 3

6ro,lo nr*{"
.r t e\
=
_l ü'(,)
20 a X.H +3 (" -")

{? : 3n -6
l8 = 3n =J Gql ::::'l ho1 g uJ.{,.",
L,/
2() -- 1.\ " \.3
r____-/
V_t
6 verfice(
r)
")u1 \.,\*. ¡".i{,,, Con.'{ruiY [or

r)
,,h.
t\
I

i-
¡

, ,,
a'
 [Büten Zar]
"E1-ereler¿ rq
[Link]
Menu q o,lrn^.,,rg , C.réo un rti." fl, 3.

{
,

{¡ L* ¡**i{ole
f*r*o, [Link] fr.o{o 3- reg*[or cú*1 q u*nd,.ug]

'ile\ = f g.(*\
x€-v v

:\e\ = 3 -q

tle\ = al -i oo se pr,n{u f$rrmcrr

 [Büten Zar]
r,iir.
[Link]
. ,

Menu
!- ,
;i cuán'l6r -.[Link]! e 1iu.,.n 6.oáo pa, 6i 6 t,.n. I ,iJ,..
l" ¡rolu
F*, ] 6 {i u.,e n ui r{ic.g

,1 vár{i"" {. 6 {[Link]. td, ?ar *, ñ*t li.r,.o 6ro{o irmpo"r.

E,, G \.t n I'i ' uí.tri.,' J.:' g*ll ¡rñPo.r :E=*l . Q-I
ot";§r.*
ac Par

el rmlsr¡o ulrlto no sc .r."{,

V*.V fl(,).t;t* =6ñ \J
/'
\-,---'*

,"f '

S'j.) + ¡1(x) = €D -\ Qlt-t ?nR. +:=¡ g!(r) IAR

0Í') irrnpar e-)

8;(.
) ¡*f...

L fJ,".rl., , porq e\ uur{t". Pq

r se t;ene

+ A; (') ¡ ñ-l ?t Qs Far

0.(.\
i:
É.
w
p'
':il:- Et*un... ro\o \oy { ,{Jice, , dr
8."}" pon ,^ 6.
 [Büten Zar]
Menu
[Link]

.{,*á [ es *l rn"J'xi ¡.r,o oni"n go' i b f e ¡lo'rs

Lrn
ü."{; cetl 'l? o.¡J".s s ¡ {".!o,
")¿
[Link] ul.{*.qs liu.r*,'' Xroüo mndYor o i1"ctl a 31

r\e\ = I
xett
qr{*}

3t{ : n.3 + hz\ * n:5

i+n..\+nu.S
"=
r, r"
[-
t
el o'rüe n e5 r{.
1.,=

t) ¿
[x is1. oln,n t'nf" con ti.I",o "ont,tü i. udr{i"e5 I E
", (&§o o{,rn "t; uo
.ono{.u i' lo .

_ *={r

\r'
"br

-*r-**-*f
..f'".-=-=*-- -
,"
4o

{0
 [Büten Zar]
F
Erercr"io t3 Menu [Link]

Poro tu§o nolu'o\ trlr n>\ .o^.{ rd? ü un nrJo €oñcxo a* r*6rl".r y €0n ¡
*i,liou r.

rt; t\
A-=-.
./\
r'rl¡
2,\.¿',

¿---'"{:. I
"'I''. I
v
ft:(

n"B

ss cro Cn I or,.t"., untenJo uí.{,.u, ogreslor lo n*)

flrcrf"
 [Büten Zar]
Eíer"ic,o - ltl Menu [Link]

D.*',uort.. 1u. {olo {rafo coñ¿(o coñ 2 o rmaE v{.r{r..r 1;,n. d* uu.J,ors
(.on ,.1 r¡nr( rmo g*o J,

Consítn*o g(u, e )

V , ev , tr(x) ( tvl -r po.. lu"l.* nin¡un uá.{,.. {irne

o.
¡ro{"

tlorn*.', ct' \oE

'á'titt, nJ .le 6
cons (
co{mg
¡u [o rmcg y q. lo,
[Link] pn,, ].1
$

( n*r\ [Link] ,.,i üos .

Entt¡n ces P." p*lo*... h.y po" fo mn*nos 2 *ir{¡.., cc}n ei *,, i srmo
6ro{o.
 [Büten Zar]
Elererclg !?
Menu [Link]

\ uár{tcns {" X.uáo ?. uírti .r, d*

&.t,1 . [Link],
t ,á.t i." ¿- 61"J" 3
2 u{nt,"u, {o ¡ro..1o t\
I ui rtice ü. X'*L u

1\E\
f- fl'(*,
3

1"\ E\ 1,,ñ + ? Lt + 3.1 I \ ? + 5.1

z\eI n+ t+8 +8
- _:t
["?"IEi
n + 2\ | --. lÉ[ : h+2{

C*:*Yno es un [Link] lvl = lrl +r

lvt o -t..?-3- rr
2.

tlvl = n+2§ ¡2

+t+6) h +?6
"(urn*1
dt + tn .: t\ + ?6

b-1"-1¡T h"y to ho¡os

 [Büten Zar]
Menu [Link]
LJ ¿'ci cio {6

J-rt raco rn i do E,rctc.¡[Link]

-"A - B *r E*a 0 "*_r(. --rB 'I

Gc2
,--B focr¡ rr¡Jo 8., elc.i ano
6,'^
'r|
¡/ - -
\.-
".r
6,\
1'
iit,...':
.,-
A g _.*_r C *:-.-} A ***r F __r C _*r } --+ F -*_r E -+ )
't ,/ -{
6r \ F<-* -"' ' ,106.
r..
g

\.,

,/L
GL

A
citcui"to Evctqr¡a¡o

A, --lC ---r B
-. B -+C ---r F . ¡ 6 *r É + F -*-r H
-+J
-*t 6 -i o -+ A.
 [Büten Zar]
[Link]
Menu

6
H

[l t¿acrrr l]o vcr d.. D' a G

l) -¡ E rF *r G .-.-.. H * 1 J ---+ { --{ B ** (

-. ___a A ___i
I *r ( _-_r 0 -*r H

F .--r $ ---l É
 [Büten Zar]
Menu
[Link]
G) Y*e V qr(*) : o-,t ._) kn 't.náo..¡r*uílu e",le,¡ono e=" n-,r cs pqr
U t".

§) Poro. k?

kn n >2 Sr 1rL,e.a recorrrJo .ul. r,ono luntrín erac'lomen'le I uiJ,.r, Ju

itnpor y cotrno en k^ {oJor los ud'{;t'' l',ntt' ul nrnisrmo
6roüo
d". uár{¡.el Ju
==t no h,.L.,.n srlo*o^J" 6ra{o
ir,¡[Link],
[.^]"
 [Büten Zar]
Er¿rci cro {q
[Link]
Menu ?iel = f qr(x)
x€v

.) K6 *-{ rt5 _ rCgt¡lcry

ur,.o.,'-{ro.
tt
\J tuero n[ r{c*rr¡¡lx coh rrndxi*o lorrg,lr,?

:\.el = 6. '--) t \E\ . [Link] + t S

I ! R. . Eut¿
\ \,. i * rr: I
.\ j¡(,, l(f
tt
b vcrlie€r
dnU., *1o 9 v{r{,u,.r d* B,oJo r'ff}far
t-l
á
I thi, X \ +5 = i, l
E.'{on.*, ul ,*.rr., Jo J. rrn.i x, rno It noilrd ci 'l*

ü K6 É4 ? 'requlur

[Link][ = s.l :lel = 6.6 + ?.1

[g]-.-.Ls ¡? .
q5

4 k,o t- .unu\o.

?\r\ = {o' \ Llri B. B+ 1.1

[L.r
q.8 +9 : \1

J) kr", ("ro - rl - [Link],

ü
(tn -? + ? (?.n
:1e\ =
?* . {to-,i ::=:t t I al = -t'!

_..t
:it.t : \"rt-bn+\ * \n -t
r

f ltl = \n -\n +?

',J.!_a_.no;tn 1r j
Eterclcto ?O Menu
[Büten Zar]
-+--_-+
[Link]
Se.o. e) R les eon¡snlor J* [Link]*, É,r\eriuoo, 7 \'ler*,ril{oniqnai ..npuJir.r**nlu
Uu un Xtt*rt¡rlo
I
de un "-C
¡ralo
Bn {\}t . o{ro e\ ¡t\r y J,o 4n [^t
r\
I".
t \'lr :
¡
t1,

i
I

,¡

f(-'---- -:'?
H\r I'r
i\.
I
I
I

1'.., ¡

L^H : C"G É^ tL
 [Büten Zar]
t-rcre te to Zl Menu
[Link]
L...roJ r* r¡n ei ¿\o Ho.*¡\{onioho. §i exrs\e.
faro, ".r&o {'d; l. l* f,g"r^ 6
6 F
a .e
j Sr rc¿ü)r *. B ',
ro A D eli,mint el ..Jo J. lo,
- *:dC
¡

t arist*, i*ni{t^{es eñ B ? c quedo qo,*o uár{¡¿" o..},.rlolo

14"
i.,,i
i ,.'
D
r*-\ ñ§ \.,*V ci.\o h.r'^r\t'ntono
ti
\.
L*. ar r slrrr 1ue trr,ci*tn cn un vár{¡cr J. 2
¡.olo
{,onrr, e<ior
1un
Q".k uñ ud'l¡." s, n unirst , ¿t rrrñpostLl, *l ","1o

E".r{* .t Hoo^[Link].
"1o
 [Büten Zar]
Ejercler o 4_ [Link]
Menu
Kle
Ges k -_ , ru6rl*r.
V >t 3
¿
c u úi*q , ü. \nt' Stquienles es .un,[Link] .rft","',1. p*rq G f.n¡o rrn .io[o
ü
1r.
tt*,114,'raru.

T¿oret,o. (v)
gr(r\ + g,

Corolqr ¡o
{r(wi L

\.1 1,\( l v
 [Büten Zar]
[Link]

Menu Matemática Discreta I - 2011

Práctico 8
Grafos: subgrafo, subgrafos inducidos y recubridores.
Isomorfismos y grafo complemento.
Grado y grafos regulares.
Recorridos y circuitos eulerianos y ciclos hamiltonianos.

Aclaraciones y Definiciones

Todos los grafos de este práctico se suponen simples, es decir, sin aristas múltiples.
Un vértice es aislado si no es adyacente a ningún otro.
El grafo complemento Ḡ de un grafo G = (V, E) se define como Ḡ = (V, V (2) \ E) donde V (2) = {{u, v} :
u, v ∈ V, u 6= v}. Un grafo G se dice autocomplementario si es isomorfo a Ḡ.
Si G1 = (V1 , E1 ) y G2 = (V2 , E2 ) son dos grafos vértices disjuntos (V1 ∩ V2 = ∅), entonces su grafo unión
G1 ∪ G2 se define como G1 ∪ G2 = (V1 ∪ V2 , E1 ∪ E2 ).
Denotaremos κ(G) a la cantidad de componentes conexas de G.
Un grafo se dice k–regular si todos sus vértices tiene grado k. Un vértice colgante es un vértice de grado 1.

Ejercicios
Ejercicio 1 Sea G el grafo de la Figura 1 (a).
a)¿Cuántos subgrafos conexos de G tienen 4 vértices e incluyen un ciclo?
b) Describa el subgrafo G1 de G (Figura 1 (b)) como un subgrafo inducido y en términos de la eliminación
de vértices de G.
c) Ídem para el subgrafo G2 (Figura 1 (c)).
d) Trace el subgrafo de G inducido por el conjunto de vértices U = {b, c, d, f, i, j}.
e) Sean e1 y e2 las artistas {a, c} y {a, d} respectivamente del grafo G. Trace los siguientes subgrafos de G:
(i) (G − e1 ) − e2 ; (ii) (G − e2 ) − e1 ; (iii) G − {e1 , e2 }.

G G1 G2
a a

b b b

g c g c d
f f f
d d

i
i i
h j h j h j

(a) (b) (c)

Figura 1:

f) Encuentre un subgrafo de G que no sea inducido.

g) ¿Qué condición o condiciones debe cumplir un subgrafo para no ser inducido?
h) ¿Cuántos subgrafos recubridores tiene G?
i) ¿Cuántos de los subgrafos anteriores son conexos?
j) ¿cuántos subgrafos de la parte h) tienen el vértice a como vértice aislado?

1
 [Büten Zar]
[Link]

Figura 2:

Ejercicio 2 Encuentre un grafo G que tenga dos vértices u y v tales que

κ(G − u) = κ(G) κ(G − v) > κ(G)

Ejercicio 3 Encuentre todos los árboles no isomorfos con 6 vértices.

Ejercicio 4 (2do parcial 2001) Halle el número de subgrafos conexos recubridores no isomorfos del grafo de
la Figura 2.

Ejercicio 5 Para cada par de grafos de la Figura 3 determine si los grafos son o no isomorfos.

a b a b
c d c d

e f e f
g h g h
(a)
a

f b 1 2
5

6
e c 4 3

d
(b)
a

f b 1 2
5

c 4 6 3
e

d
(c)

Figura 3:

Ejercicio 6 a) Demuestre que dos grafos son isomorfos si y solo si sus grafos complemento lo son.
b)( 2do parcial curso 2000) ¿Cuáles de los grafos de la Figura 4 son isomorfos?
c) Determine el número de aristas de Ḡ en función del número de aristas de G.
d) Determine el número de aristas de un grafo autocomplementario de orden n.
e) Construya un grafo autocomplementario de orden 4 y otro de orden 5.
f) Determine para qué valores de n existe un grafo autocomplementario de orden n.

Ejercicio 7 Pruebe que Kn posee tres subgrafos dos a dos isomorfos y arista disjuntos si y sólo si n es de
la forma 3k o 3k + 1.

2
 [Büten Zar]
[Link]

Figura 4:

Ejercicio 8 a) Halle el grado de cada vértice del grafo de la Figura 2.

b) ¿Cuántas aristas tiene dicho grafo?
c) ¿Cuántos vértices de grado impar tiene?

Ejercicio 9 a) Determine el orden de un grafo 3–regular con 9 aristas.

b) Ídem con 10 aristas, dos vértices de grado 4 y los demás de grado 3.
c) ¿Existen tales grafos? En caso afirmativo construirlos.

Ejercicio 10 En una clase con 9 alumnos, cada alumno le manda 3 tarjetas de navidad a otros 3. ¿Es
posible que cada alumno reciba tarjetas de los mismos 3 compañeros a los cuales él le mando una?

Ejercicio 11 Sea G un grafo con n vértices. ¿Cuántos vértices de Ḡ tienen grado par si G tiene un sólo
vértice de grado par?

Ejercicio 12 a) ¿Cuál es el máximo orden posible para un grafo con 17 aristas si todos sus vértices tienen
grado mayor o igual a 3?
b) ¿Existe algún grafo con dicha cantidad de vértices? En caso afirmativo construirlo.

Ejercicio 13 Para todo natural par n ≥ 4 construya un grafo conexo 3–regular con n vértices.

Ejercicio 14 Demuestre que todo grafo conexo con 2 o más vértices tiene dos vértices con el mismo grado.

Ejercicio 15 ¿Cuántas hojas (vértices colgantes) tiene un árbol con cuatro vértices de grado 2, uno de
grado 3, dos de grado 4 y uno de grado 5?

Ejercicio 16 Halle un recorrido o un circuito euleriano para cada grafo de la Figura 5 o demuestre que no
existe.

Figura 5:

Ejercicio 17 Encuentre un recorrido euleriano para G = (V, E) con V = {a, b, c, d, e, f, g, h, i, j} y

E = {ab, ac, ai, aj, bc, cd, ci, de, df, dg, dh, ef, f g, f h, gh, hi, ij}.

Ejercicio 18 a) Determine los valores de n para los cuales el grafo completo Kn tendrá un circuito eule-
riano.
b) ¿Para cuáles n tiene Kn un recorrido euleriano?

3
 [Büten Zar]
[Link]

Figura 6:

Ejercicio 19 Encuentre la longitud máxima de un recorrido en a) K6 ; b) K8 ; c) K10 ; d) K2n , n ∈ N.

Ejercicio 20 Sea E y H los conjuntos de grafos Eulerianos y Hamiltonianos respectivamente. Dé un ejemplo
de un grafo en E \ H, otro en H \ E y otro en E ∩ H.

Ejercicio 21 Encuentre un ciclo Hamiltoniano, si existe, para cada grafo de la Figura 6.

Ejercicio 22 (Examen febrero 2010) Dados k ≥ 2, v ≥ 3 y un grafo G, k-regular con v vértices diga cuáles
de las siguientes es condición suficiente para que G tenga un ciclo Hamiltoniano.
a) 2k ≥ v; b) k ≤ v; c) 2k < v; d) 2k 6= v

Ejercicio 23 (2do parcial 2009)

1. Sea G = (V, E) un grafo sin lazos, con V = {v1 , v2 , ..., vn }. Llamamos H = (VH , EH ) al grafo inducido
por {v3 , ..., vn }. Probar que si gr(v1 ) + gr(v2 ) < n entonces |EH | + gr(v1 ) + gr(v2 ) < C2n−1 + 2.
2. Sea G = (V, E) un grafo sin lazos con |V | = n > 2 y |E| ≥ C2n−1 + 2. Probar que G tiene un ciclo
hamiltoniano.

Sugerencias
Ejercicio 6 f) Demuestre que n debe ser de la forma 4k o 4k + 1. Para n = 4k, generalice la estructura
del grafo autocomplementario de orden 4 agrupando los vértices en cuatro grupos. Para n = 4k + 1 agregue
un vértice al grafo anterior y únalo en forma adecuada.