All Questions
Tagged with eulerian-path trees
7
questions
0
votes
0
answers
33
views
Spanning Trees with 1/2 the edges in a Eulerian Graph
I was attempting the following problem:
Let $G$ be a connected simple graph. (a) If $G$ is eulerian with an even number of vertices, then it has a spanning subgraph $G'$ such that every node $i$ has ...
- 11
0
votes
1
answer
40
views
counting Eulerian circuits on complete directed graph
I have a complete directed graph $G$ (including self-loops). How can I count the number of Eulerian circuits on $G$?
For example, in the simple case of $n=2$, there are clearly 4 Eulerian circuits. ...
- 1
1
vote
1
answer
272
views
Prove that an undirected connected graph $G$ contains an Euler circuit by some properties of its fundamental cut-set matrix and connectivity.
Let $G$ be an undirected connected graph. $\forall v∈V(G)$, $G-v$ (remove the node and all of its relevant edges from the graph) is still a connected graph. Besides, the fundamental cut-set matrix $S$ ...
- 13
0
votes
1
answer
35
views
Show that this graph is a tree
Suppose we have a directed multigraph (a graph with loops and parallel edges), with vertex set $V=\{v_1,v_2,\cdots,v_n\}$, such that $d^+(v_i)=d^-(v_i)$ for every $i=1,2,\cdots,n$, i.e. indegree of ...
- 12.7k
1
vote
1
answer
495
views
A vertex $v$ is extendible if and only if $G − v$ is a forest.
I need help understanding the solution to this problem. This problem has been answered here, however, my doubt is not addressed.
Problem: Let $G$ be a connected Eulerian graph with at least $3$ ...
- 476
2
votes
2
answers
1k
views
Find the number of degree 1 vertices in terms of n and d
Fix an integer $d>1$. Let $G$ be a tree with $n$ vertices, and every vertex can have either degree $1$ or $d$. Find the number of degree $1$ vertices in terms of $d$ and $n$.
I've been working on ...
- 151
0
votes
1
answer
460
views
Tree & Euler, Hamilton paths [closed]
If a tree on n vertices (n>1) has 2 pendant vertices, does it have Euler path or Hamilton path?
- 451