<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@8bd7329c25a44de9a08b05d7013d0481" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Introduction</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@350e004533044dc6ae9a8e30c5ca7ecb">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@350e004533044dc6ae9a8e30c5ca7ecb" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Read <a href="/assets/courseware/v1/a8bb399f99cf7bb3bea98d0512a41aa5/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Session20.pdf" target="[object Object]">Chapter 11.7–11.9 (PDF)</a> of <em>Mathematics for Computer Science</em> for 2.9 Coloring & Connectivity.</p>
<p>View the <a href="/assets/courseware/v1/5a63aa03ffc9cbbf7df354da0c8f8348/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_cp20.pdf" target="[object Object]">Section 2.9 In-Class Questions (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@8486504fd1d7480b957b0bfd9eeff970" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | Coloring</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@abe372e4de80403791590c225bb950c6">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@abe372e4de80403791590c225bb950c6" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Coloring</h3>
<div
id="video_abe372e4de80403791590c225bb950c6"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:Penh4mv5gAg", "ytTestTimeout": 1500, "end": 0.0, "autoplay": false, "captionDataDir": null, "savedVideoPosition": 0.0, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@abe372e4de80403791590c225bb950c6/handler/publish_completion", "showCaptions": "true", "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@abe372e4de80403791590c225bb950c6/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_simplecoloring_video_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@abe372e4de80403791590c225bb950c6/handler/transcript/translation/__lang__", "autoAdvance": false, "start": 0.0, "autohideHtml5": false, "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@abe372e4de80403791590c225bb950c6/handler/xmodule_handler/save_user_state", "duration": 0.0, "transcriptLanguages": {"en": "English"}, "saveStateEnabled": false, "ytMetadataEndpoint": "", "transcriptLanguage": "en", "speed": null, "generalSpeed": 1.0, "poster": null, "recordedYoutubeIsAvailable": true}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="abe372e4de80403791590c225bb950c6"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_abe372e4de80403791590c225bb950c6">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_abe372e4de80403791590c225bb950c6">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_simplecoloring_video_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@abe372e4de80403791590c225bb950c6/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@abe372e4de80403791590c225bb950c6/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@d433fe6fc76041868f07dfc97346ceaa">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@d433fe6fc76041868f07dfc97346ceaa" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/e1b3579886ca096deadf9ac644817d70/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Coloring.pdf" target="[object Object]">Coloring (PDF)</a></p>
<p><a href="/assets/courseware/v1/30824e1165544629fb0cd3ea8f3ee967/asset-v1:OCW+6.042J+2T2019+type@asset+block/Coloring_2.9_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@bab83c2f1992470e8d6861f865ce19e0" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Chromatic Number</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@4368c23ff9df4d72a225a9a25b6e7945">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@4368c23ff9df4d72a225a9a25b6e7945" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_4368c23ff9df4d72a225a9a25b6e7945" class="problems-wrapper" role="group"
aria-labelledby="4368c23ff9df4d72a225a9a25b6e7945-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@4368c23ff9df4d72a225a9a25b6e7945" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@4368c23ff9df4d72a225a9a25b6e7945/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="3"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="4368c23ff9df4d72a225a9a25b6e7945-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@4368c23ff9df4d72a225a9a25b6e7945-problem-progress" tabindex="-1">
Chromatic Number
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@4368c23ff9df4d72a225a9a25b6e7945-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_4368c23ff9df4d72a225a9a25b6e7945_2_1">
<fieldset aria-describedby="status_4368c23ff9df4d72a225a9a25b6e7945_2_1">
<legend id="4368c23ff9df4d72a225a9a25b6e7945_2_1-legend" class="response-fieldset-legend field-group-hd">1. A graph with maximum degree <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>k</mi>
</math> must have a chromatic number <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo>&#8805;<!-- &#8805; --></mo>
<mi>k</mi>
</math>.</legend>
<div class="field">
<input type="radio" name="input_4368c23ff9df4d72a225a9a25b6e7945_2_1" id="input_4368c23ff9df4d72a225a9a25b6e7945_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="4368c23ff9df4d72a225a9a25b6e7945_2_1-choice_0-label" for="input_4368c23ff9df4d72a225a9a25b6e7945_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_4368c23ff9df4d72a225a9a25b6e7945_2_1"> True
</label>
</div>
<div class="field">
<input type="radio" name="input_4368c23ff9df4d72a225a9a25b6e7945_2_1" id="input_4368c23ff9df4d72a225a9a25b6e7945_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="4368c23ff9df4d72a225a9a25b6e7945_2_1-choice_1-label" for="input_4368c23ff9df4d72a225a9a25b6e7945_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_4368c23ff9df4d72a225a9a25b6e7945_2_1"> False
</label>
</div>
<span id="answer_4368c23ff9df4d72a225a9a25b6e7945_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_4368c23ff9df4d72a225a9a25b6e7945_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_4368c23ff9df4d72a225a9a25b6e7945_3_1" id="label_4368c23ff9df4d72a225a9a25b6e7945_3_1">2. What is the chromatic number for a Wheel graph with <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
</math> vertices, where <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
</math> is even?</label>
<select name="input_4368c23ff9df4d72a225a9a25b6e7945_3_1" id="input_4368c23ff9df4d72a225a9a25b6e7945_3_1" aria-describedby="status_4368c23ff9df4d72a225a9a25b6e7945_3_1">
<option value="option_4368c23ff9df4d72a225a9a25b6e7945_3_1_dummy_default">Select an option</option>
<option value="n"> n</option>
<option value="3"> 3</option>
<option value="4"> 4</option>
<option value="n+1"> n+1</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_4368c23ff9df4d72a225a9a25b6e7945_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_4368c23ff9df4d72a225a9a25b6e7945_3_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_4368c23ff9df4d72a225a9a25b6e7945_4_1" id="label_4368c23ff9df4d72a225a9a25b6e7945_4_1">3. How many colors do you need to color a complete graph with <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
</math> vertices?</label>
<select name="input_4368c23ff9df4d72a225a9a25b6e7945_4_1" id="input_4368c23ff9df4d72a225a9a25b6e7945_4_1" aria-describedby="status_4368c23ff9df4d72a225a9a25b6e7945_4_1">
<option value="option_4368c23ff9df4d72a225a9a25b6e7945_4_1_dummy_default">Select an option</option>
<option value="n"> n</option>
<option value="n/2"> n/2</option>
<option value="3"> 3</option>
<option value="4"> 4</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_4368c23ff9df4d72a225a9a25b6e7945_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_4368c23ff9df4d72a225a9a25b6e7945_4_1"/>
</div></div>
<div class="solution-span">
<span id="solution_4368c23ff9df4d72a225a9a25b6e7945_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Chromatic Number" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_4368c23ff9df4d72a225a9a25b6e7945" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_4368c23ff9df4d72a225a9a25b6e7945">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="4368c23ff9df4d72a225a9a25b6e7945-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="4368c23ff9df4d72a225a9a25b6e7945-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="4368c23ff9df4d72a225a9a25b6e7945-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="4368c23ff9df4d72a225a9a25b6e7945-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@e61995047fdd445c939a161f1b2d5304" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | Connectivity</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@0bb1c8eb7e464879bf6969ddc03d9c3a">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@0bb1c8eb7e464879bf6969ddc03d9c3a" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Connectivity</h3>
<div
id="video_0bb1c8eb7e464879bf6969ddc03d9c3a"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:TIQ3xN38jgM", "ytTestTimeout": 1500, "end": 0.0, "autoplay": false, "captionDataDir": null, "savedVideoPosition": 0.0, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0bb1c8eb7e464879bf6969ddc03d9c3a/handler/publish_completion", "showCaptions": "true", "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0bb1c8eb7e464879bf6969ddc03d9c3a/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_simpleconnect_video_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0bb1c8eb7e464879bf6969ddc03d9c3a/handler/transcript/translation/__lang__", "autoAdvance": false, "start": 0.0, "autohideHtml5": false, "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0bb1c8eb7e464879bf6969ddc03d9c3a/handler/xmodule_handler/save_user_state", "duration": 0.0, "transcriptLanguages": {"en": "English"}, "saveStateEnabled": false, "ytMetadataEndpoint": "", "transcriptLanguage": "en", "speed": null, "generalSpeed": 1.0, "poster": null, "recordedYoutubeIsAvailable": true}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="0bb1c8eb7e464879bf6969ddc03d9c3a"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_0bb1c8eb7e464879bf6969ddc03d9c3a">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_0bb1c8eb7e464879bf6969ddc03d9c3a">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_simpleconnect_video_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0bb1c8eb7e464879bf6969ddc03d9c3a/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0bb1c8eb7e464879bf6969ddc03d9c3a/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@d5ce9f847dad40c5b455fb5639d62486">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@d5ce9f847dad40c5b455fb5639d62486" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/70d5facd79e5f7ed13dce8f3cafb6339/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Connectivity.pdf" target="[object Object]">Connectivity (PDF)</a></p>
<p><a href="/assets/courseware/v1/46d8a30560fb159848f2fbe8afe5813b/asset-v1:OCW+6.042J+2T2019+type@asset+block/Connectivity_2.9_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@9911a984e5a141aaa9cb587aa74c58f3" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | k-Connectivity</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@30acfcd4d9c44ce09c4c2f3505b1e3a8">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@30acfcd4d9c44ce09c4c2f3505b1e3a8" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">k-Connectivity </h3>
<div
id="video_30acfcd4d9c44ce09c4c2f3505b1e3a8"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:5wCZqdCDafc", "ytTestTimeout": 1500, "end": 0.0, "autoplay": false, "captionDataDir": null, "savedVideoPosition": 0.0, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@30acfcd4d9c44ce09c4c2f3505b1e3a8/handler/publish_completion", "showCaptions": "true", "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@30acfcd4d9c44ce09c4c2f3505b1e3a8/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia600207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_simple_kconnect_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@30acfcd4d9c44ce09c4c2f3505b1e3a8/handler/transcript/translation/__lang__", "autoAdvance": false, "start": 0.0, "autohideHtml5": false, "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@30acfcd4d9c44ce09c4c2f3505b1e3a8/handler/xmodule_handler/save_user_state", "duration": 0.0, "transcriptLanguages": {"en": "English"}, "saveStateEnabled": false, "ytMetadataEndpoint": "", "transcriptLanguage": "en", "speed": null, "generalSpeed": 1.0, "poster": null, "recordedYoutubeIsAvailable": true}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="30acfcd4d9c44ce09c4c2f3505b1e3a8"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_30acfcd4d9c44ce09c4c2f3505b1e3a8">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_30acfcd4d9c44ce09c4c2f3505b1e3a8">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia600207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_simple_kconnect_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@30acfcd4d9c44ce09c4c2f3505b1e3a8/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@30acfcd4d9c44ce09c4c2f3505b1e3a8/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@e601f431aee546cd9aee45efb2f48f05">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@e601f431aee546cd9aee45efb2f48f05" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/c7a6e379e1e1c93a4c3db0816420d188/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_kconnectivity.pdf" target="[object Object]">k-Connectivity (PDF)</a></p>
<p><a href="/assets/courseware/v1/df72a203bf59dbcb1d95b649acc3ba17/asset-v1:OCW+6.042J+2T2019+type@asset+block/kConnectivity_2.9_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@289a4c5f678b4ac8a165fbb8cf2fe3a9" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | k-Connected [Optional]</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@7f856d26908c4ce49924b88479c53d10">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@7f856d26908c4ce49924b88479c53d10" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_7f856d26908c4ce49924b88479c53d10" class="problems-wrapper" role="group"
aria-labelledby="7f856d26908c4ce49924b88479c53d10-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@7f856d26908c4ce49924b88479c53d10" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@7f856d26908c4ce49924b88479c53d10/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="7f856d26908c4ce49924b88479c53d10-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@7f856d26908c4ce49924b88479c53d10-problem-progress" tabindex="-1">
k-Connected
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@7f856d26908c4ce49924b88479c53d10-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_7f856d26908c4ce49924b88479c53d10_2_1" id="label_7f856d26908c4ce49924b88479c53d10_2_1">1. Which of the following statements is valid?</label>
<select name="input_7f856d26908c4ce49924b88479c53d10_2_1" id="input_7f856d26908c4ce49924b88479c53d10_2_1" aria-describedby="status_7f856d26908c4ce49924b88479c53d10_2_1">
<option value="option_7f856d26908c4ce49924b88479c53d10_2_1_dummy_default">Select an option</option>
<option value="k-edge-connected IMPLIES k-vertex-connected"> k-edge-connected IMPLIES k-vertex-connected</option>
<option value="k-vertex-connected IMPLIES k-edge-connected"> k-vertex-connected IMPLIES k-edge-connected</option>
<option value="k-edge-connected IFF k-vertex-connected"> k-edge-connected IFF k-vertex-connected</option>
<option value="k-edge-connected IMPLIES (k+1)-edge-connected"> k-edge-connected IMPLIES (k+1)-edge-connected</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_7f856d26908c4ce49924b88479c53d10_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_7f856d26908c4ce49924b88479c53d10_2_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_7f856d26908c4ce49924b88479c53d10_3_1" id="label_7f856d26908c4ce49924b88479c53d10_3_1">2. The complete graph on n vertices is_____</label>
<select name="input_7f856d26908c4ce49924b88479c53d10_3_1" id="input_7f856d26908c4ce49924b88479c53d10_3_1" aria-describedby="status_7f856d26908c4ce49924b88479c53d10_3_1">
<option value="option_7f856d26908c4ce49924b88479c53d10_3_1_dummy_default">Select an option</option>
<option value="n/2-connected"> n/2-connected</option>
<option value="n-connected"> n-connected</option>
<option value="(n-1)-connected"> (n-1)-connected</option>
<option value="1-connected"> 1-connected</option>
<option value="not connected"> not connected</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_7f856d26908c4ce49924b88479c53d10_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_7f856d26908c4ce49924b88479c53d10_3_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="k-Connected" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_7f856d26908c4ce49924b88479c53d10" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_7f856d26908c4ce49924b88479c53d10">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="7f856d26908c4ce49924b88479c53d10-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="7f856d26908c4ce49924b88479c53d10-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="7f856d26908c4ce49924b88479c53d10-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="7f856d26908c4ce49924b88479c53d10-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@86a162f435894facaf89890cdd0f7807" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Graph Coloring I</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a9397cb6395e461db14c7c303f661b05">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a9397cb6395e461db14c7c303f661b05" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_a9397cb6395e461db14c7c303f661b05" class="problems-wrapper" role="group"
aria-labelledby="a9397cb6395e461db14c7c303f661b05-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a9397cb6395e461db14c7c303f661b05" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@a9397cb6395e461db14c7c303f661b05/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="a9397cb6395e461db14c7c303f661b05-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@a9397cb6395e461db14c7c303f661b05-problem-progress" tabindex="-1">
Graph Coloring I
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@a9397cb6395e461db14c7c303f661b05-problem-progress"></div>
<div class="problem">
<div>
<p><img height="207" width="377" src="/assets/courseware/v1/7afa27edbeffc0f2cc89ae2419a541fc/asset-v1:OCW+6.042J+2T2019+type@asset+block/6.042_Unit_II_2.96.jpg" alt="Graph Coloring I"/></p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_a9397cb6395e461db14c7c303f661b05_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_a9397cb6395e461db14c7c303f661b05_2_1" id="label_a9397cb6395e461db14c7c303f661b05_2_1">What is the chromatic number of the above graph?</label>
<input type="text" name="input_a9397cb6395e461db14c7c303f661b05_2_1" id="input_a9397cb6395e461db14c7c303f661b05_2_1" aria-describedby="status_a9397cb6395e461db14c7c303f661b05_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_a9397cb6395e461db14c7c303f661b05_2_1"/>
<span class="status unanswered" id="status_a9397cb6395e461db14c7c303f661b05_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_a9397cb6395e461db14c7c303f661b05_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_a9397cb6395e461db14c7c303f661b05_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Graph Coloring I" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_a9397cb6395e461db14c7c303f661b05" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_a9397cb6395e461db14c7c303f661b05">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="a9397cb6395e461db14c7c303f661b05-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a9397cb6395e461db14c7c303f661b05-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a9397cb6395e461db14c7c303f661b05-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a9397cb6395e461db14c7c303f661b05-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@f077eafdf5954455b00aa662a59ebbbc" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Graph Coloring II</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a75a512cb99849ce83eea8019853c615">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a75a512cb99849ce83eea8019853c615" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_a75a512cb99849ce83eea8019853c615" class="problems-wrapper" role="group"
aria-labelledby="a75a512cb99849ce83eea8019853c615-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a75a512cb99849ce83eea8019853c615" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@a75a512cb99849ce83eea8019853c615/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="a75a512cb99849ce83eea8019853c615-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@a75a512cb99849ce83eea8019853c615-problem-progress" tabindex="-1">
Graph Coloring II
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@a75a512cb99849ce83eea8019853c615-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_a75a512cb99849ce83eea8019853c615_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_a75a512cb99849ce83eea8019853c615_2_1" id="label_a75a512cb99849ce83eea8019853c615_2_1">What is the chromatic number of an acyclic graph?</label>
<input type="text" name="input_a75a512cb99849ce83eea8019853c615_2_1" id="input_a75a512cb99849ce83eea8019853c615_2_1" aria-describedby="status_a75a512cb99849ce83eea8019853c615_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_a75a512cb99849ce83eea8019853c615_2_1"/>
<span class="status unanswered" id="status_a75a512cb99849ce83eea8019853c615_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_a75a512cb99849ce83eea8019853c615_2_1" class="answer"/>
</div>
</div><div class="solution-span">
<span id="solution_a75a512cb99849ce83eea8019853c615_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Graph Coloring II" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_a75a512cb99849ce83eea8019853c615" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_a75a512cb99849ce83eea8019853c615">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="a75a512cb99849ce83eea8019853c615-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a75a512cb99849ce83eea8019853c615-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a75a512cb99849ce83eea8019853c615-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a75a512cb99849ce83eea8019853c615-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@88070ac818654ccd84b7830a3c043643" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Connected Components Among the Integers</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@baa63c873a8344d5a97009f171a1d3a7">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@baa63c873a8344d5a97009f171a1d3a7" data-request-token="c0d01fd8e12111ef99830affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_baa63c873a8344d5a97009f171a1d3a7" class="problems-wrapper" role="group"
aria-labelledby="baa63c873a8344d5a97009f171a1d3a7-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@baa63c873a8344d5a97009f171a1d3a7" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@baa63c873a8344d5a97009f171a1d3a7/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="baa63c873a8344d5a97009f171a1d3a7-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@baa63c873a8344d5a97009f171a1d3a7-problem-progress" tabindex="-1">
Connected Components Among the Integers
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@baa63c873a8344d5a97009f171a1d3a7-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_baa63c873a8344d5a97009f171a1d3a7_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_baa63c873a8344d5a97009f171a1d3a7_2_1" id="label_baa63c873a8344d5a97009f171a1d3a7_2_1">Let <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>g</mi>
</math> be the graph whose vertices are the integers, where an edge exists between every pair of vertices <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>i</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>j</mi>
</math> iff <math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mi>i</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mi>j</mi>
<mrow class="MJX-TeXAtom-ORD">
<mo stretchy="false">|</mo>
</mrow>
<mo>=</mo>
<mn>6</mn>
</math>.
<br/>
<br/>
1. How many connected components does <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>g</mi>
</math> have?</label>
<input type="text" name="input_baa63c873a8344d5a97009f171a1d3a7_2_1" id="input_baa63c873a8344d5a97009f171a1d3a7_2_1" aria-describedby="status_baa63c873a8344d5a97009f171a1d3a7_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_baa63c873a8344d5a97009f171a1d3a7_2_1"/>
<span class="status unanswered" id="status_baa63c873a8344d5a97009f171a1d3a7_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_baa63c873a8344d5a97009f171a1d3a7_2_1" class="answer"/>
</div>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Connected Components Among the Integers" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_baa63c873a8344d5a97009f171a1d3a7" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_baa63c873a8344d5a97009f171a1d3a7">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="baa63c873a8344d5a97009f171a1d3a7-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="baa63c873a8344d5a97009f171a1d3a7-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="baa63c873a8344d5a97009f171a1d3a7-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="baa63c873a8344d5a97009f171a1d3a7-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>