\documentclass[11pt]{scrartcl} \usepackage[headheight=1pt, includeheadfoot, headsep=1cm, top=1.5cm, bottom=1.3cm, left=2cm, right=2cm]{geometry} \usepackage{mathtools} \usepackage{amsmath,amsthm, amscd, amssymb, amsfonts} \usepackage[english]{babel} \usepackage{fancyhdr} \usepackage{enumitem} \setlist{itemsep=0.5em} \usepackage{xcolor} \definecolor{forestgreen}{rgb}{0.13, 0.55, 0.13} \usepackage[colorlinks = true, linkcolor = forestgreen, urlcolor = forestgreen, citecolor = forestgreen, anchorcolor = forestgreen]{hyperref} \usepackage{multicol} \usepackage{multienum} \usepackage{euler} \usepackage[OT1]{eulervm} \renewcommand{\rmdefault}{pplx} \usepackage{tikz} \usepackage{mathabx} %\usepackage{lastpage} %% header, footer definitions \def\course{MATH 314} \def\courselink{https://www.gsanmarco.com/graph-theory} \def\assignment{HW \#4} \def\assignlink{hw04.tex} \def\due{Due on Feb 14} \pagestyle{fancy} \fancyhead[L]{\course} \fancyhead[C]{\assignment} \fancyhead[R]{\due} %\renewcommand{\footrulewidth}{0.4pt} %\fancyfoot{} %\fancyfoot[R]{\fontsize{8}{10} \selectfont Page \thepage~of \pageref{LastPage}} %\fancyfoot[L]{\fontsize{10}{12} \selectfont Source file available at \href{\courselink / %{\textbf{\courselink}}} %% environments % theorem style \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{claim}[theorem]{Claim} \newtheorem{defn}[theorem]{Definition} % definition style \theoremstyle{definition} \newtheorem{problem}{Problem} \newtheorem{Solution}{Solution} % custom \newenvironment{solution}{\noindent\textbf{Solution.}}{\qed} %% custom commands \newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality \newcommand*{\eps}{\varepsilon} % prettier epsilon \newcommand*{\R}{\mathbb{R}} % real numbers \newcommand*{\C}{\mathbb{C}} % complex numbers \newcommand*{\Q}{\mathbb{Q}} % rational numbers \newcommand*{\Z}{\mathbb{Z}} % integers \newcommand*{\N}{\mathbb{N}} % natural numbers \newcommand*{\F}{\mathbb{F}} % field \newcommand*{\family}{\mathcal{F}} % family \newcommand*{\GL}{\mathbf{GL}} % general linear group \newcommand*{\what}[1]{\widehat{#1}} % wider hat \newcommand*{\wbar}[1]{\overline{#1}} % wider bar \newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal \newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf \newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb % operators \let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability \DeclareMathOperator*{\E}{\mathbb{E}} % expectation \DeclareMathOperator*{\Var}{\mathbf{Var}} % variance \DeclareMathOperator*{\Span}{span} % span \DeclareMathOperator{\tr}{tr} % trace \DeclareMathOperator{\rank}{rank} % rank \DeclareMathOperator{\supp}{supp} % support \DeclareMathOperator{\diam}{diam} \begin{document} \noindent Unless explicitly requested by a problem, do not include sketches as part of your proof. You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem. \vskip10pt \begin{problem}[2 pts] Let $G$ and $H$ be graphs. A \emph{graph homomorphism} from $G$ to $H$ is a function $f\colon V(G)\to V(H)$ such that $\{f(u),f(v)\}\in E(H)$ whenever $\{u,v\}\in E(G)$. Prove that a graph $G$ is bipartite if and only if there is a graph homomorphism from $G$ to $K_2$. (Note that a graph homomorphism does \emph{not} need to be a bijection and that it could be the case that $\{f(u),f(v)\}\in E(H)$ even though $\{u,v\}\notin E(G)$) \end{problem} \begin{problem}[2 pts] A graph $G$ is called \emph{self-complementary} if $G\cong\wbar G$. For example, $P_4$ and $C_5$ are self-complementary. Prove that if $G$ is a self-complementary graph on $n$ vertices, then $n$ is congruent to either $0$ or $1$ modulo $4$. \end{problem} \begin{problem}[2 pts]\label{paths} Let $T$ be a tree on $n$ vertices with $\Delta(T)\leq 2$. Prove that $T\cong P_n$. \end{problem} \begin{problem}[2 pts] Determine (with proof) all trees $T$ (up to isomorphism) on $n\geq 2$ vertices such that $\wbar T$ is also a tree. (Note: we do not require that $T\cong\wbar T$.) \end{problem} \begin{problem}[2 pts]Let $G$ and $H$ be two self-complementary graphs on disjoint vertex sets, where $H$ has even order $n$. Let $F$ be the graph obtained from $G\cup H$ by joining each vertex of $G$ to every vertex of degree less than $n/2$ in $H$. Show that $F$ is self-complementary. \emph{Hint}: A graph $F$ is self-complementary if there exists a $\varphi : V(F) \rightarrow V(F)$ such that $vw\in E(F)$ if and only if $\varphi(v)\varphi(w)\not\in E(F)$. \end{problem} \end{document} Let $G$ be a connected graph and let $S$ be any subset of edges of $G$. Show that $G$ has a connected, spanning subgraph $H$ such that $S\subseteq E(H)$ and if $C$ is a cycle in $H$, then $E(C) \subseteq S$.